Magic Powder - 2 CodeForces - 670D2(2점)
CodeForces - 670D2
The term of this problem is the same as the previous one, the only exception — increased restrictions. Input
The first line contains two positive integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109) — the number of ingredients and the number of grams of the magic powder.
The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ 109), where the i-th number is equal to the number of grams of the i-th ingredient, needed to bake one cookie.
The third line contains the sequence b1, b2, ..., bn (1 ≤ bi ≤ 109), where the i-th number is equal to the number of grams of the i-th ingredient, which Apollinaria has.
Output
Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.
Example
Input
1 1000000000
1
1000000000
Output
2000000000
Input
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1
Output
0
Input
3 1
2 1 4
11 3 16
Output
4
Input
4 3
4 3 5 6
11 12 14 20
Output
3
code:
#include
#include
#include
using namespace std;
typedef long long ll;
ll n,k,a[100002],b[100002];
int main(){
cin >> n >> k;
ll i;
for(i = 0; i < n; i++){
cin >> a[i];
}
for(i = 0; i < n; i++){
cin >> b[i];
}//
ll left = 0,right = 2000000000;// ， ，
ll ans = 0;
while(left <= right){
ll mid = (left+right)/2;
ll m = k;
int flag = 1;
for(i = 0;i < n; i++){//
if(a[i] * mid > b[i]){// ，
if(m - (a[i] * mid - b[i]) >= 0){// ，
m -= (a[i] * mid - b[i]);
}
else{
flag = 0;
break;// ，
}
}
//else
}
if(flag){// ，
ans = mid;
left = mid + 1;
}
else{//
right = mid - 1;
}
}
printf("%lld
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
