Submission #734511

#	Time	Username	Problem	Language	Result	Execution time	Memory
734511		1075508020060209tc	Self Study (JOI22_ho_t2)	C++14	100 / 100	508 ms	20748 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int __int128
int n;int m;
int ar[300005];
int br[300005];
int cr[300005];

int ok(int mi){

int lft=0;
for(int i=1;i<=n;i++){
    int nd=(mi+ar[i]-1)/ar[i];
    if(nd<=m){
        cr[i]=0;
        lft+=m-nd;
    }else{
        cr[i]=mi-ar[i]*m;
    }
}
for(int i=1;i<=n;i++){
    if(cr[i]==0){continue;}
    lft-=(cr[i]+br[i]-1)/br[i];
}
if(lft>=0){return 1;}
return 0;
}

int read(){
long long ret;
cin>>ret;
return ret;
}

signed main(){
    
//cin>>n>>m;
n=read();m=read();
for(int i=1;i<=n;i++){
    ar[i]=read();
}
for(int i=1;i<=n;i++){
    br[i]=read();
    ar[i]=max(ar[i],br[i]);
}


int l=1;int r=1e18;
while(l<r){
    int mi=l+(r-l+1)/2;
    if(ok(mi)){
        l=mi;
    }else{
        r=mi-1;
    }
}
long long t=l;
cout<<t<<endl;


}

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