# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
77438 | 2018-09-27T20:23:47 Z | Vardanyan | Watching (JOI13_watching) | C++14 | 1000 ms | 32152 KB |
#include <bits/stdc++.h> using namespace std; const int N = 2005; int a[N]; int mxshort[N]; int mxlong[N]; int dp[N][N]; int main(){ int n,p,q; scanf("%d%d%d",&n,&p,&q); for(int i = 1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); int l = 1; int r = 1000*1000*1000; int ans = r; while(l<=r){ int m = (l+r)/2; memset(mxlong,0,sizeof(mxlong)); memset(mxshort,0,sizeof(mxshort)); memset(dp,0,sizeof(dp)); int now = n; int noww = n; for(int i = n;i>=1;i--){ while(!(abs(a[i]-a[now])+1<=m)) now--; mxshort[i] = now; while(!(abs(a[i]-a[noww])+1<=2*m)) noww--; mxlong[i] = noww; } bool f = false; dp[0][0] = 1; int u = 5; while(u--){ for(int i = 0;i<=min(n,p);i++){ for(int j = 0;j<=min(n,q);j++){ int pos = max(1,dp[i][j]); dp[i+1][j] = max(dp[i+1][j],mxshort[pos]+1); dp[i][j+1] = max(dp[i][j+1],mxlong[pos]+1); } } } for(int i = 0;i<=p;i++){ for(int j = 0;j<=q;j++) if(dp[i][j]>n) f = true; } if(f){ ans = m; r = m-1; } else l = m+1; } cout<<ans<<endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 42 ms | 16092 KB | Output is correct |
2 | Correct | 40 ms | 16252 KB | Output is correct |
3 | Correct | 41 ms | 16252 KB | Output is correct |
4 | Runtime error | 33 ms | 32004 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 32136 KB | Output is correct |
2 | Correct | 42 ms | 32136 KB | Output is correct |
3 | Execution timed out | 1070 ms | 32152 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |