Submission #756553

#TimeUsernameProblemLanguageResultExecution timeMemory
756553michaoSelf Study (JOI22_ho_t2)C++14
100 / 100
314 ms11464 KiB
#include <bits/stdc++.h> #define int long long #define mp make_pair #define pb push_back #define ld long double #define pii pair<int,int> #define sz(x) (int)x.size() #define piii pair<pii,pii> #define precise cout<<fixed<<setprecision(10) #define st first #define nd second #define ins insert #define vi vector<int> #define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int MAX=3e5+5; const int inf=(int)3e18+9; int a[MAX],b[MAX]; int n,m; int gora(int x,int y){ if (x%y==0)return x/y; return x/y+1; } bool check(int mid){ int balans=0; for (int i=1;i<=n;i++){ int wale=max(a[i],b[i]); int need=gora(mid,wale); if (need<=m){ balans+=m-need; } else{ int sum=mid-wale*m; assert(sum>=0LL); int odejmij=gora(sum,b[i]); if (balans<-inf)return false; balans-=odejmij; } } return balans>=0; } int32_t main() { BOOST; cin>>n>>m; for (int i=1;i<=n;i++)cin>>a[i]; for (int i=1;i<=n;i++)cin>>b[i]; int ans2=inf; if (m==1){ for (int i=1;i<=n;i++)ans2=min(ans2,max(a[i],b[i])); } int ip=0,ik=inf; while (ip+1<ik){ int mid=(ip+ik)>>1; if (check(mid))ip=mid; else ik=mid; } cout<<ip; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...