Submission #380773

#TimeUsernameProblemLanguageResultExecution timeMemory
380773mariowongWatching (JOI13_watching)C++14
0 / 100
1092 ms20176 KiB
#include <bits/stdc++.h> using namespace std; int l,r,mid,n,p,q,a[2005],dp[2005][2005]; vector <int> v; deque <int> dq; int main(){ ios::sync_with_stdio(false); cin >> n >> p >> q; for (int i=1;i<=n;i++){ cin >> a[i]; } sort(a+1,a+1+n); for (int i=1;i<=n;i++){ for (int j=i;j<=n;j++){ v.push_back(a[j]-a[i]+1); } } sort(v.begin(),v.end()); l=0; r=(int)v.size()-1; while (l < r){ mid=(l+r)/2; for (int i=0;i<=min(n,q);i++){ //used how many large for (int j=1;j<=n;j++){ dp[i][j]=1e9; } } for (int i=0;i<=min(n,q);i++){ //used how many large if (i > 0){ dq.push_back(0); for (int j=1;j<=n;j++){ while (!dq.empty() && a[j]-a[dq.front()+1]+1 > 2*(v[mid]/2+v[mid]%2)) dq.pop_front(); if (dq.empty()){ l=mid+1; while (!dq.empty()) dq.pop_front(); goto out; } else dp[i][j]=dp[i-1][dq.front()]; while (!dq.empty() && dp[i-1][j] <= dp[i-1][dq.back()]) dq.pop_back(); dq.push_back(j); } while (!dq.empty()) dq.pop_back(); } dq.push_back(0); for (int j=1;j<=n;j++){ while (!dq.empty() && a[j]-a[dq.front()+1]+1 > (v[mid]/2+v[mid]%2)) dq.pop_front(); if (!dq.empty()) dp[i][j]=min(dp[i][j],dp[i][dq.front()]+1); while (!dq.empty() && dp[i][j] <= dp[i][dq.back()]) dq.pop_back(); dq.push_back(j); } while (!dq.empty()) dq.pop_back(); } /* cout << l << " " << r << "\n"; for (int i=1;i<=min(n,q);i++){ //used how many large for (int j=1;j<=n;j++){ cout << dp[i][j] << " "; } cout << "\n"; }*/ if (dp[min(n,q)][n] <= p) r=mid; else l=mid+1; out:; } cout << v[l]/2+v[l]%2 << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...