Submission #341536

#TimeUsernameProblemLanguageResultExecution timeMemory
341536iliccmarkoWatching (JOI13_watching)C++14
100 / 100
428 ms31980 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; vector<ll> a; ll dp[N][N]; int main() { ios cin>>n>>p>>q; a.pb(0); for(int i = 1;i<=n;i++) { ll x; cin>>x; a.pb(x); } sort(all(a)); if(p+q>=n) { cout<<1; return 0; } ll ans = 1e9; ll l = 1; ll r = 1e9; while(l<=r) { ll mid = (r+l)/2; //mid = 4; for(int i = 0;i<=n;i++) for(int j = 0;j<=n;j++) dp[i][j] = INF; for(int i = 0;i<=n;i++) dp[0][i] = 0; for(int i = 1;i<=n;i++) { int w = a[i] - mid; int ind = upper_bound(all(a), w) - a.begin(); if(ind) { ind--; for(int j = 0;j<=n;j++) { dp[i][j] = dp[ind][j] + 1; } } else { for(int j = 0;j<=n;j++) { dp[i][j] = 1; if(j) dp[i][j] = 0; } } ind = upper_bound(all(a), a[i] - 2*mid) - a.begin(); if(ind) { ind--; for(int j = 1;j<=n;j++) { dp[i][j] = min(dp[i][j], dp[ind][j-1]); } } else { for(int j = 1;j<=n;j++) dp[i][j] = 0; } } bool moze = false; for(int i = 0;i<=n;i++) { if(i<=q&&dp[n][i]<=p) moze = true; } /*for(int i = 1;i<=n;i++) { for(int j = 0;j<=n;j++) cout<<dp[i][j]<<" "; cout<<endl; }*/ if(moze) { ans = mid; r = mid - 1; } else { l = mid + 1; } //break; } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...