Submission #624429

#	Time	Username	Problem	Language	Result	Execution time	Memory
624429		QwertyPi	Self Study (JOI22_ho_t2)	C++14	100 / 100	574 ms	11504 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e5 + 10;
int a[N], b[N];

int n, m;

bool check(int x){
	__int128_t remain = n * m;
	for(int i = 0; i < n; i++){
		__int128_t y = x;
		if(b[i] > a[i]) a[i] = b[i];
		__int128_t r1 = min((y + a[i] - 1) / a[i], (__int128_t) m);
		remain -= r1;
		y -= r1 * a[i];
		__int128_t r2 = (y + b[i] - 1) / b[i];
		if(r2 >= INT64_MAX) return false;
		remain -= max((__int128_t) 0LL, r2);
	}
	return remain >= 0;
}

int32_t main(){
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	for(int i = 0; i < n; i++){
		cin >> b[i];
	}
	int l = 0, r = 1e18;
	while(l != r){
		if(check((l + r + 1) / 2)){
			l = (l + r + 1) / 2;
		}else{
			r = (l + r + 1) / 2 - 1;
		}
	}
	cout << l << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 9 / 9