# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
77751 | 2018-09-30T07:52:28 Z | nxteru | Watching (JOI13_watching) | C++14 | 690 ms | 16592 KB |
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; int n,p,q,a[2005],dp[2005][2005]; bool solve(int w){ if(p+q>=n)return true; for(int i=0;i<=n;i++){ for(int j=0;j<=p;j++){ dp[i][j]=-1; } } dp[0][p]=q; for(int i=0;i<n;i++){ for(int j=0;j<=p;j++){ if(dp[i][j]>=0){ if(dp[i][j]>0){ int k=upper_bound(a,a+n,a[i]+w*2-1)-a; dp[k][j]=max(dp[k][j],dp[i][j]-1); } if(j>0){ int k=upper_bound(a,a+n,a[i]+w-1)-a; dp[k][j-1]=max(dp[k][j-1],dp[i][j]); } } } } for(int i=0;i<=p;i++){ if(dp[n][i]>=0)return true; } return false; } int main(void){ scanf("%d%d%d",&n,&p,&q); for(int i=0;i<n;i++)scanf("%d",a+i); sort(a,a+n); int r=0,l=1000000000; while(l-r>1){ int m=(r+l)/2; if(solve(m))l=m; else r=m; } printf("%d\n",l); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 760 KB | Output is correct |
2 | Correct | 2 ms | 760 KB | Output is correct |
3 | Correct | 2 ms | 760 KB | Output is correct |
4 | Correct | 2 ms | 760 KB | Output is correct |
5 | Correct | 2 ms | 760 KB | Output is correct |
6 | Correct | 2 ms | 760 KB | Output is correct |
7 | Correct | 2 ms | 944 KB | Output is correct |
8 | Correct | 3 ms | 1048 KB | Output is correct |
9 | Correct | 2 ms | 1048 KB | Output is correct |
10 | Correct | 3 ms | 1048 KB | Output is correct |
11 | Correct | 4 ms | 1048 KB | Output is correct |
12 | Correct | 4 ms | 1060 KB | Output is correct |
13 | Correct | 2 ms | 1060 KB | Output is correct |
14 | Correct | 2 ms | 1064 KB | Output is correct |
15 | Correct | 2 ms | 1064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 8616 KB | Output is correct |
2 | Correct | 2 ms | 8616 KB | Output is correct |
3 | Correct | 3 ms | 8616 KB | Output is correct |
4 | Correct | 2 ms | 8616 KB | Output is correct |
5 | Correct | 3 ms | 8616 KB | Output is correct |
6 | Correct | 3 ms | 8616 KB | Output is correct |
7 | Correct | 13 ms | 8824 KB | Output is correct |
8 | Correct | 109 ms | 9728 KB | Output is correct |
9 | Correct | 219 ms | 14740 KB | Output is correct |
10 | Correct | 323 ms | 16592 KB | Output is correct |
11 | Correct | 149 ms | 16592 KB | Output is correct |
12 | Correct | 690 ms | 16592 KB | Output is correct |
13 | Correct | 11 ms | 16592 KB | Output is correct |
14 | Correct | 12 ms | 16592 KB | Output is correct |
15 | Correct | 12 ms | 16592 KB | Output is correct |