# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
51450 | 2018-06-18T02:58:11 Z | Vinhspm | Watching (JOI13_watching) | C++14 | 1000 ms | 8892 KB |
#include<bits/stdc++.h> using namespace std; #define ll long long #define ii pair<int, int> #define fi first #define se second #define pb push_back const int N = 2009; const int oo = 1e9; const int mod = 1e9 + 7; int n, P, Q; int a[N], dp[N][N]; bool check(int x) { // base for(int i = 0; i <= P; ++ i) for(int j = 0; j <= Q; ++j) dp[i][j] = -1; dp[0][0] = 0; for(int i = 0; i <= P; ++i) for(int j = 0; j <= Q; ++j){ if(i > 0) { int cur = dp[i - 1][j] + 1; int nexpos = a[cur] + x - 1; int pos = upper_bound(a + 1, a + n + 1, nexpos) - a - 1; dp[i][j] = max(dp[i][j], pos); } if(j > 0) { int cur = dp[i][j - 1] + 1; int nexpos = a[cur] + 2*x - 1; int pos = upper_bound(a + 1, a + n + 1, nexpos) - a - 1; dp[i][j] = max(dp[i][j], pos); } if(dp[i][j] == n) return true; } return false; } signed main() { //freopen("test.txt", "r", stdin); //ios_base::sync_with_stdio(false); //cin.tie(0); cout.tie(0); scanf("%d%d%d", &n, &P, &Q); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); sort(a + 1, a + n + 1); a[0] = 0; if(P + Q >= n) { printf("1"); return 0; } //cout << check(3) << '\n'; return 0; int l = 1, r = oo; while(r > l + 1) { int mid = (l + r)/ 2; if(check(mid)) r = mid; else l = mid; } for(int i = l; i <= r; ++i) if(check(i)) { printf("%d", i); return 0; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 2 ms | 356 KB | Output is correct |
3 | Correct | 2 ms | 408 KB | Output is correct |
4 | Correct | 2 ms | 408 KB | Output is correct |
5 | Correct | 2 ms | 408 KB | Output is correct |
6 | Correct | 2 ms | 536 KB | Output is correct |
7 | Correct | 2 ms | 600 KB | Output is correct |
8 | Correct | 2 ms | 600 KB | Output is correct |
9 | Correct | 2 ms | 600 KB | Output is correct |
10 | Correct | 2 ms | 600 KB | Output is correct |
11 | Correct | 3 ms | 800 KB | Output is correct |
12 | Correct | 3 ms | 800 KB | Output is correct |
13 | Correct | 2 ms | 800 KB | Output is correct |
14 | Correct | 2 ms | 800 KB | Output is correct |
15 | Correct | 2 ms | 800 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 800 KB | Output is correct |
2 | Correct | 2 ms | 800 KB | Output is correct |
3 | Correct | 2 ms | 800 KB | Output is correct |
4 | Correct | 2 ms | 800 KB | Output is correct |
5 | Correct | 2 ms | 800 KB | Output is correct |
6 | Correct | 2 ms | 800 KB | Output is correct |
7 | Correct | 3 ms | 800 KB | Output is correct |
8 | Correct | 193 ms | 1476 KB | Output is correct |
9 | Correct | 174 ms | 3940 KB | Output is correct |
10 | Correct | 183 ms | 8892 KB | Output is correct |
11 | Correct | 151 ms | 8892 KB | Output is correct |
12 | Execution timed out | 1079 ms | 8892 KB | Time limit exceeded |
13 | Halted | 0 ms | 0 KB | - |