Submission #594626

#	Time	Username	Problem	Language	Result	Execution time	Memory
594626		1ne	Self Study (JOI22_ho_t2)	C++14	100 / 100	366 ms	10852 KiB

Main

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n,m;cin>>n>>m;
	vector<long long>arr(n);
	for (int i = 0;i<n;++i)cin>>arr[i];
	vector<long long>brr(n);
	for (int i = 0;i<n;++i)cin>>brr[i];
	long long left = 0,right = 1e18;
	long long ans = 0;
	while(left<=right){
		long long mid = (left + right)>>1;
		bool okay = true;
		long long chance = 0;
		for (int i = 0;i<n;++i){
			long long temp = (mid + max(arr[i],brr[i]) - 1)/max(arr[i],brr[i]);
			chance+=max(0LL,m - temp);
		}
		for (int i = 0;i<n;++i){
			if ((mid + m - 1) / m > max(arr[i],brr[i])){
				long long cur = m * max(arr[i],brr[i]);
				long long temp = min(chance,(mid - cur + brr[i] - 1) / brr[i]);
				cur+=temp * brr[i];
				if (cur < mid)okay = false;
				chance-=temp;
			}
		}
		if (okay){
			left = mid + 1;
			ans = mid;
		}
		else{
			right = mid - 1;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

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