Submission #526380

#	Time	Username	Problem	Language	Result	Execution time	Memory
526380		mosiashvililuka	Self Study (JOI22_ho_t2)	C++14	100 / 100	267 ms	11968 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,lef,rig,mid,A[300009],B[300009],f[300009],M;
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>M;
	for(i=1; i<=a; i++) cin>>A[i];
	for(i=1; i<=a; i++) cin>>B[i];
	for(i=1; i<=a; i++) A[i]=max(A[i],B[i]);
	lef=0;rig=1000000000000000009LL;
	while(1){
		if(lef+1>=rig) break;
		mid=(lef+rig)/2;
		for(i=1; i<=a; i++){
			f[i]=mid;
		}
		zx=0;
		for(i=1; i<=a; i++){
			if(f[i]>A[i]*M){
				f[i]-=A[i]*M;
			}else{
				c=f[i]/A[i];
				if(f[i]%A[i]!=0) c++;
				zx+=M-c;
				f[i]=max(0LL,f[i]-c*A[i]);
			}
		}
		xc=0;
		for(i=1; i<=a; i++){
			if(f[i]<=0) continue;
			c=f[i]/B[i];
			if(f[i]%B[i]!=0) c++;
			xc+=c;
			if(xc>zx) break;
		}
		if(zx>=xc){
			lef=mid;
		}else{
			rig=mid;
		}
	}
	cout<<lef;
	return 0;
}

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