Algorithm

D2. Magic Powder - 2
time limit per test
1 second
memory limit per test
256 megabytes
Problem liink- https://codeforces.com/contest/670/problem/D2
input
standard input
output
standard output

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.

Examples
input
Copy
1 1000000000
1
1000000000
output
Copy
2000000000
input
Copy
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1
output
Copy
0
input
Copy
3 1
2 1 4
11 3 16
output
Copy
4
input
Copy
4 3
4 3 5 6
11 12 14 20
output
Copy
3

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>

using namespace std;

const int N = 1e5 + 1;
long long n, k;
int a[N], b[N];

bool can(long long mid) {
	long long m = k;

	for(int i = 0; i < n; i++) {
		long long need = (long long) a[i] * mid - b[i];

		if(need < 0)
			continue;

		m -= need;

		if(m < 0)
			return false;
	}

	return true;
}

int main() {
	cin >> n >> k;

	for(int i = 0 ; i < n; i++)
		cin >> a[i];

	for(int i = 0 ; i < n; i++)
		cin >> b[i];

	long long l = 0, r = 2e9, res = 0;

	while(l <= r) {
		int mid = (l + r) / 2;
		if(can(mid)> {
			l = mid + 1;
			res = mid;
		} else
			r = mid - 1;
	}

	cout << res << endl;

	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
1 1000000000
1
1000000000

Output

x
–
+
cmd
2000000000
Advertisements

Demonstration

Codeforces Solution-Magic Powder - 2-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+