# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
237566 | 2020-06-07T10:55:02 Z | jingyanyu | Watching (JOI13_watching) | C++17 | 226 ms | 16124 KB |
#include <bits/stdc++.h> using namespace std; const int N = 2005; int a[N], 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 + n + 1); int l = 1, r = 1000000000, res; while(r - l >= 0) { int mid = (l + r) >> 1; dp[0][0] = 0; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=n+1; for (int i = 1; i <= n; i++) { int pp = 1, pq = 1; for (int j = i; j >= 1; j--) { if (a[i] - a[j] + 1 <= mid) pp = j; if (a[i] - a[j] + 1 <= 2*mid) pq = j; } dp[i][0] = dp[pq - 1][0] + 1; for (int j = 1; j <= min(i, p); j++) { dp[i][j] = min(dp[pp - 1][j - 1], dp[pq - 1][j] + 1); } } int mn = dp[n][0]; for (int i = 1; i <= n; i++) { mn = min(mn, dp[n][i]); } if (mn <= q) { r = mid - 1; res = mid; } else { l = mid + 1; } } printf("%d\n", res); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 768 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 768 KB | Output is correct |
5 | Correct | 5 ms | 768 KB | Output is correct |
6 | Correct | 6 ms | 768 KB | Output is correct |
7 | Correct | 5 ms | 768 KB | Output is correct |
8 | Correct | 5 ms | 768 KB | Output is correct |
9 | Correct | 5 ms | 768 KB | Output is correct |
10 | Correct | 5 ms | 768 KB | Output is correct |
11 | Correct | 5 ms | 768 KB | Output is correct |
12 | Correct | 5 ms | 768 KB | Output is correct |
13 | Correct | 5 ms | 768 KB | Output is correct |
14 | Correct | 5 ms | 768 KB | Output is correct |
15 | Correct | 5 ms | 768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 148 ms | 16084 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 215 ms | 16000 KB | Output is correct |
4 | Correct | 220 ms | 16120 KB | Output is correct |
5 | Correct | 152 ms | 16120 KB | Output is correct |
6 | Correct | 220 ms | 16000 KB | Output is correct |
7 | Correct | 156 ms | 16120 KB | Output is correct |
8 | Correct | 161 ms | 16000 KB | Output is correct |
9 | Correct | 197 ms | 16124 KB | Output is correct |
10 | Correct | 226 ms | 16000 KB | Output is correct |
11 | Correct | 156 ms | 16120 KB | Output is correct |
12 | Correct | 207 ms | 16000 KB | Output is correct |
13 | Correct | 149 ms | 16000 KB | Output is correct |
14 | Correct | 156 ms | 16120 KB | Output is correct |
15 | Correct | 152 ms | 16120 KB | Output is correct |