| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 428722 | 2021-06-15T14:03:56 Z | shenxy | Sparklers (JOI17_sparklers) | C++11 | 457 ms | 8260 KB |
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const long long INF = 1LL << 60;
int N, K;
long long T, X[1000], m, dpt[1000][1000];
long long dp(int a, int b) {
if (a == K - 1 && b == K - 1) return 2 * m * T;
if (a == b) return -INF;
if (dpt[a][b] != -1) return dpt[a][b];
return dpt[a][b] = max(dp(a + 1, b) + (X[a] - X[a + 1]) / 2 < 0 ? -INF : dp(a + 1, b) + (X[a] - X[a + 1]) / 2, dp(a, b - 1) + (X[b - 1] - X[b]) / 2 < 0 ? -INF : dp(a, b - 1) + (X[b - 1] - X[b]) / 2) + 2 * m * T;
}
int main() {
scanf("%d %d %lld", &N, &K, &T);
for (int i = 0; i < N; ++i) scanf("%lld", &X[i]), X[i] *= 2;
long long l = 0, u = 10000000000 / T;
while (l != u) {
m = (l + u) / 2;
memset(dpt, -1, sizeof dpt);
if (dp(0, N - 1) < 0) l = m + 1;
else u = m;
}
printf("%lld", l);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 25 ms | 8096 KB | Output is correct |
| 2 | Correct | 28 ms | 8012 KB | Output is correct |
| 3 | Correct | 22 ms | 8108 KB | Output is correct |
| 4 | Correct | 23 ms | 8088 KB | Output is correct |
| 5 | Correct | 34 ms | 8096 KB | Output is correct |
| 6 | Correct | 38 ms | 8012 KB | Output is correct |
| 7 | Correct | 34 ms | 8112 KB | Output is correct |
| 8 | Correct | 25 ms | 8012 KB | Output is correct |
| 9 | Correct | 35 ms | 8012 KB | Output is correct |
| 10 | Correct | 33 ms | 8012 KB | Output is correct |
| 11 | Correct | 23 ms | 8012 KB | Output is correct |
| 12 | Correct | 29 ms | 8088 KB | Output is correct |
| 13 | Correct | 26 ms | 8012 KB | Output is correct |
| 14 | Correct | 27 ms | 8012 KB | Output is correct |
| 15 | Correct | 34 ms | 8108 KB | Output is correct |
| 16 | Correct | 35 ms | 8088 KB | Output is correct |
| 17 | Correct | 24 ms | 8012 KB | Output is correct |
| 18 | Correct | 22 ms | 8012 KB | Output is correct |
| 19 | Correct | 28 ms | 8012 KB | Output is correct |
| 20 | Correct | 27 ms | 8108 KB | Output is correct |
| 21 | Correct | 23 ms | 8012 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 25 ms | 8096 KB | Output is correct |
| 2 | Correct | 28 ms | 8012 KB | Output is correct |
| 3 | Correct | 22 ms | 8108 KB | Output is correct |
| 4 | Correct | 23 ms | 8088 KB | Output is correct |
| 5 | Correct | 34 ms | 8096 KB | Output is correct |
| 6 | Correct | 38 ms | 8012 KB | Output is correct |
| 7 | Correct | 34 ms | 8112 KB | Output is correct |
| 8 | Correct | 25 ms | 8012 KB | Output is correct |
| 9 | Correct | 35 ms | 8012 KB | Output is correct |
| 10 | Correct | 33 ms | 8012 KB | Output is correct |
| 11 | Correct | 23 ms | 8012 KB | Output is correct |
| 12 | Correct | 29 ms | 8088 KB | Output is correct |
| 13 | Correct | 26 ms | 8012 KB | Output is correct |
| 14 | Correct | 27 ms | 8012 KB | Output is correct |
| 15 | Correct | 34 ms | 8108 KB | Output is correct |
| 16 | Correct | 35 ms | 8088 KB | Output is correct |
| 17 | Correct | 24 ms | 8012 KB | Output is correct |
| 18 | Correct | 22 ms | 8012 KB | Output is correct |
| 19 | Correct | 28 ms | 8012 KB | Output is correct |
| 20 | Correct | 27 ms | 8108 KB | Output is correct |
| 21 | Correct | 23 ms | 8012 KB | Output is correct |
| 22 | Correct | 219 ms | 8152 KB | Output is correct |
| 23 | Correct | 149 ms | 8140 KB | Output is correct |
| 24 | Correct | 185 ms | 8148 KB | Output is correct |
| 25 | Correct | 373 ms | 8172 KB | Output is correct |
| 26 | Correct | 361 ms | 8172 KB | Output is correct |
| 27 | Correct | 442 ms | 8140 KB | Output is correct |
| 28 | Correct | 396 ms | 8140 KB | Output is correct |
| 29 | Correct | 402 ms | 8168 KB | Output is correct |
| 30 | Correct | 384 ms | 8180 KB | Output is correct |
| 31 | Correct | 375 ms | 8172 KB | Output is correct |
| 32 | Correct | 404 ms | 8184 KB | Output is correct |
| 33 | Correct | 457 ms | 8184 KB | Output is correct |
| 34 | Correct | 379 ms | 8176 KB | Output is correct |
| 35 | Correct | 383 ms | 8140 KB | Output is correct |
| 36 | Correct | 350 ms | 8172 KB | Output is correct |
| 37 | Correct | 344 ms | 8260 KB | Output is correct |
| 38 | Correct | 374 ms | 8172 KB | Output is correct |
| 39 | Correct | 377 ms | 8140 KB | Output is correct |
| 40 | Correct | 415 ms | 8164 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 25 ms | 8096 KB | Output is correct |
| 2 | Correct | 28 ms | 8012 KB | Output is correct |
| 3 | Correct | 22 ms | 8108 KB | Output is correct |
| 4 | Correct | 23 ms | 8088 KB | Output is correct |
| 5 | Correct | 34 ms | 8096 KB | Output is correct |
| 6 | Correct | 38 ms | 8012 KB | Output is correct |
| 7 | Correct | 34 ms | 8112 KB | Output is correct |
| 8 | Correct | 25 ms | 8012 KB | Output is correct |
| 9 | Correct | 35 ms | 8012 KB | Output is correct |
| 10 | Correct | 33 ms | 8012 KB | Output is correct |
| 11 | Correct | 23 ms | 8012 KB | Output is correct |
| 12 | Correct | 29 ms | 8088 KB | Output is correct |
| 13 | Correct | 26 ms | 8012 KB | Output is correct |
| 14 | Correct | 27 ms | 8012 KB | Output is correct |
| 15 | Correct | 34 ms | 8108 KB | Output is correct |
| 16 | Correct | 35 ms | 8088 KB | Output is correct |
| 17 | Correct | 24 ms | 8012 KB | Output is correct |
| 18 | Correct | 22 ms | 8012 KB | Output is correct |
| 19 | Correct | 28 ms | 8012 KB | Output is correct |
| 20 | Correct | 27 ms | 8108 KB | Output is correct |
| 21 | Correct | 23 ms | 8012 KB | Output is correct |
| 22 | Correct | 219 ms | 8152 KB | Output is correct |
| 23 | Correct | 149 ms | 8140 KB | Output is correct |
| 24 | Correct | 185 ms | 8148 KB | Output is correct |
| 25 | Correct | 373 ms | 8172 KB | Output is correct |
| 26 | Correct | 361 ms | 8172 KB | Output is correct |
| 27 | Correct | 442 ms | 8140 KB | Output is correct |
| 28 | Correct | 396 ms | 8140 KB | Output is correct |
| 29 | Correct | 402 ms | 8168 KB | Output is correct |
| 30 | Correct | 384 ms | 8180 KB | Output is correct |
| 31 | Correct | 375 ms | 8172 KB | Output is correct |
| 32 | Correct | 404 ms | 8184 KB | Output is correct |
| 33 | Correct | 457 ms | 8184 KB | Output is correct |
| 34 | Correct | 379 ms | 8176 KB | Output is correct |
| 35 | Correct | 383 ms | 8140 KB | Output is correct |
| 36 | Correct | 350 ms | 8172 KB | Output is correct |
| 37 | Correct | 344 ms | 8260 KB | Output is correct |
| 38 | Correct | 374 ms | 8172 KB | Output is correct |
| 39 | Correct | 377 ms | 8140 KB | Output is correct |
| 40 | Correct | 415 ms | 8164 KB | Output is correct |
| 41 | Incorrect | 7 ms | 8140 KB | Output isn't correct |
| 42 | Halted | 0 ms | 0 KB | - |