Submission #51430

#TimeUsernameProblemLanguageResultExecution timeMemory
51430Flying_dragon_02Watching (JOI13_watching)C++14
100 / 100
448 ms32252 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int,int> ii; long long l,r,n,p,q,dp[2005][2005],nxt[2005][3],a[2005]; vector<long long> vec; bool check(long long w){ a[n+1] = a[n]; for(int i = 0;i<=n+1;i++){ for(int j = 0;j<=1;j++){ long long cost; if(j == 0) cost = w-1; else cost = 2*w-1; int it = upper_bound(vec.begin(),vec.end(),a[i]+cost) - vec.begin() - 1; nxt[i][j] = it; } } memset(dp,0,sizeof(dp)); for(int i = 0;i<=p;i++){ for(int j = 0;j<=q;j++){ if(i>=1) dp[i][j] = nxt[dp[i-1][j]+1][0]; if(j>=1) dp[i][j] = max(dp[i][j],nxt[dp[i][j-1]+1][1]); } } if(dp[p][q]>=n) return 1; else return 0; } int main(){ cin.tie(0),ios::sync_with_stdio(0); cin >> n >> p >> q; for(int i = 1;i<=n;i++){ cin>>a[i]; vec.pb(a[i]); } sort(a+1,a+1+n); vec.pb(-1); sort(vec.begin(),vec.end()); if(p+q>=n){ cout<<"1\n"; return 0; } l = 1; r = 1e9; while(l<r){ long long mid = (l+r)/2; if(check(mid)) r = mid; else l = mid+1; } cout<<l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...