Submission #341014

#TimeUsernameProblemLanguageResultExecution timeMemory
341014iliccmarkoWatching (JOI13_watching)C++14
0 / 100
31 ms492 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" #define INF 1000000000 #define LINF 1000000000000000LL #define pb push_back #define all(x) x.begin(), x.end() #define len(s) (int)s.size() #define test_case { int t; cin>>t; while(t--)solve(); } #define single_case solve(); #define line cerr<<"----------"<<endl; #define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); } #define mod 1000000007LL ll n, p, q; const int N = 2005; ll a[N]; int main() { ios cin>>n>>p>>q; for(int i = 0;i<n;i++) cin>>a[i]; sort(a, a+n); ll ans = 1e9; ll l = 1; ll r = 1e9; while(l<=r) { ll mid = (r+l)/2; vector<ll> v; for(int i = 0;i<n;i++) v.pb(a[i]); ll qq = q; while(true) { if(!len(v)) break; if(!qq) break; ll ima = 0; ll cnt = 0; ll maks = 0; ll levi, desni; ll pret = v[0]; ll poc = v[0]; ll kraj = 0; ll duz = 1; for(int i = 0;i<(ll)len(v);i++) { cnt++; if(v[i] - poc >= mid&&v[i] - poc + 1 <= 2 * mid) { ima = 1; if(v[i] - poc + 1 >= maks) { maks = v[i] - poc; kraj = i; duz = cnt; } } else if(v[i] - poc >= 2*mid) { cnt = 1; poc = v[i]; pret = v[i]; } pret = v[i]; } if(ima==0) break; else qq--; vector<ll> dd; for(ll i = 0;i<(ll)len(v);i++) { ll k = kraj - duz + 1; if(i<k||i>kraj) dd.pb(v[i]); } v.clear(); for(ll x : dd) v.pb(x); } if(!len(v)) { ans = mid; r = mid - 1; continue; } ll poc = v[0]; ll pret = v[0]; ll cnt = 0; for(ll x : v) { if(x - pret >= mid) { cnt++; pret = x; poc = x; } } cnt++; if(qq+p>=cnt) { ans = mid; r = mid - 1; } else { l = mid + 1; } } cout<<ans; return 0; }

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:45:12: warning: unused variable 'levi' [-Wunused-variable]
   45 |         ll levi, desni;
      |            ^~~~
watching.cpp:45:18: warning: unused variable 'desni' [-Wunused-variable]
   45 |         ll levi, desni;
      |                  ^~~~~
watching.cpp:46:12: warning: variable 'pret' set but not used [-Wunused-but-set-variable]
   46 |         ll pret = v[0];
      |            ^~~~
watching.cpp:88:12: warning: variable 'poc' set but not used [-Wunused-but-set-variable]
   88 |         ll poc = v[0];
      |            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...