Submission #1205930

#TimeUsernameProblemLanguageResultExecution timeMemory
1205930minhpkWatching (JOI13_watching)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int a,b,c; int z[1000005]; vector <int> v; vector <int> v1; bool check(int mid){ int sta=z[1]; int cnt=0; while (true){ cnt++; int pos= upper_bound(z+1,z+1+a,sta+mid-1)-z-1; if (pos==a){ break; } sta=z[pos+1]; } return cnt<=b+c; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> a >> b >> c; for (int i=1;i<=a;i++){ cin >> z[i]; } sort(z+1,z+1+a); if (b+c>a){ cout << 1 << "\n"; return 0; } int l=1; int r=1e9+7; int pos=1e9+7; while (l<=r){ int mid=(l+r)/2; if (check(mid)){ pos=mid; r=mid-1; }else{ l=mid+1; } } int sta=z[1]; while (true){ int pos1= upper_bound(z+1,z+1+a,sta+pos-1)-z-1; v.push_back(z[pos1]-sta+1); // cout << pos1 << " "; // cout << z[pos1]-z[sta] << " "; if (pos1==a){ break; } sta=z[pos1+1]; } sort(v.begin(),v.end()); for (int i=1;i<=c;i++){ int p= v.back()/2 + (v.back()%2); // cout << p << " "; v1.push_back(p); v.pop_back(); } for (int i=0;i<c;i++){ v.push_back(v1[i]); } sort(v.begin(),v.end()); cout << v.back() << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...