Submission #831134

#TimeUsernameProblemLanguageResultExecution timeMemory
831134jasminSelf Study (JOI22_ho_t2)C++17
100 / 100
211 ms11588 KiB
//JOI 2022 Final round #include<bits/stdc++.h> using namespace std; #define int long long const int INF=1e18; const int LM = LLONG_MAX; bool possible(int x, int n, int m, vector<int>& a, vector<int>& b){ int d=0; for(int i=0; i<n; i++){ if(a[i] > b[i]){ int da = (x+a[i]-1)/a[i]; int db = 0; if(da > m){ da = m; int x2 = x - (da*a[i]); assert(0<x2); db = (x2 + b[i]-1)/b[i]; } if(LM-da < d) return false; d += da; if(LM-db < d) return false; d += db; } else{ int db = (x+b[i] -1)/b[i]; if(LM-db < d) return false; d += db; } } assert(0<d); return d <= (n*m); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<int> a(n); for(int i=0; i<n; i++){ cin >> a[i]; } vector<int> b(n); for(int i=0; i<n; i++){ cin >> b[i]; } int l=1; int r=INF; int ans=1; while(l <= r ){ int mi=l+(r-l)/2; if(possible(mi, n, m, a, b)){ ans=mi; l=mi+1; } else{ r=mi-1; } } cout << ans << "\n"; }
#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...