Submission #681678

#	Time	Username	Problem	Language	Result	Execution time	Memory
681678		dsyz	Self Study (JOI22_ho_t2)	C++17	100 / 100	273 ms	13244 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (300005)
ll N,M;
ll A[MAXN], B[MAXN];
bool bs(ll mid){
	ll extra = 0;
	ll arr[N];
	bool done[N];
	memset(done,0,sizeof(done));
	for(ll i = 0;i < N;i++){
		arr[i] = mid;
	}
	for(ll i = 0;i < N;i++){
		ll minimum = mid / A[i];
		if(minimum * A[i] < mid) minimum++;
		if(minimum <= M){
			extra += (M - minimum);
			done[i] = 1;
			arr[i] = 0;
		}else{
			arr[i] -= (M * A[i]);
		}
	}
	for(ll i = 0;i < N;i++){
		if(!done[i]){
			ll minimum = arr[i] / B[i];
			if(minimum * B[i] < arr[i]) minimum++;
			if(minimum <= extra){
				extra -= minimum;
				done[i] = 1;
				arr[i] = 0;
			}else{
				return false;
			}
		}
	}
	return true;
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>M;
	for(ll i = 0;i < N;i++){
		cin>>A[i];
	}
	for(ll i = 0;i < N;i++){
		cin>>B[i];
		A[i] = max(A[i],B[i]);
	}
	ll high = 2e18 + 5;
	ll low = 0;
	while(high - low > 1){
		ll mid = (high + low) / 2;
		if(bs(mid)){
			low = mid;
		}else{
			high = mid;
		}
	}
	cout<<low<<'\n';
}

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