Submission #380775

#TimeUsernameProblemLanguageResultExecution timeMemory
380775mariowongWatching (JOI13_watching)C++14
50 / 100
1090 ms28092 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); v.push_back((a[j]-a[i]+1)/2+(a[j]-a[i]+1)%2); } } 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]) 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]) 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] << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...