| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 920614 |
2024-02-02T19:32:10 Z |
rainboy |
None (KOI17_cook) |
C++17 |
|
3 ms |
10844 KB |
#include <stdio.h>
#define N 3000
#define K 3000
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int main() {
static int ss[K][N + 1], pp[K], dp[K][N + 1], dq[K][N + 1], qu[K][N + 1], head[K], cnt[K];
int n, k, l, r, t, h, h1, h2, h3, h_, i, ans;
scanf("%d%d%d%d%d", &k, &n, &l, &r, &t);
for (h = 0; h < k; h++)
for (i = 1; i <= n; i++)
scanf("%d", &ss[h][i]), ss[h][i] += ss[h][i - 1];
for (h = 0; h < k; h++)
scanf("%d", &pp[h]), pp[h]--;
for (i = 0; i <= n; i++) {
h1 = h2 = h3 = -1;
for (h = 0; h < k; h++) {
dp[h][i] = (i == 0 ? -t : (cnt[h] ? dq[h][qu[h][head[h]]] : INF));
if (dp[h][i] != INF) {
dp[h][i] += ss[h][i];
if (h1 == -1 || dp[h1][i] > dp[h][i])
h3 = h2, h2 = h1, h1 = h;
else if (h2 == -1 || dp[h2][i] > dp[h][i])
h3 = h2, h2 = h;
else if (h3 == -1 || dp[h3][i] > dp[h][i])
h3 = h;
}
}
for (h = 0; h < k; h++) {
if (h1 != h && h1 != pp[h])
h_ = h1;
else if (h2 != h && h2 != pp[h])
h_ = h2;
else
h_ = h3;
dq[h][i] = h_ == -1 ? INF : dp[h_][i] - ss[h][i] + t;
}
for (h = 0; h < k; h++) {
if (i >= l - 1 && dq[h][i - l + 1] != INF) {
while (cnt[h] && dq[h][qu[h][head[h] + cnt[h] - 1]] >= dq[h][i - l + 1])
cnt[h]--;
qu[h][head[h] + cnt[h]++] = i - l + 1;
}
if (cnt[h] && qu[h][head[h]] == i - r)
head[h]++, cnt[h]--;
}
}
ans = INF;
for (h = 0; h < k; h++)
ans = min(ans, dp[h][n]);
printf("%d\n", ans == INF ? -1 : ans);
return 0;
}
Compilation message
cook.cpp: In function 'int main()':
cook.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | scanf("%d%d%d%d%d", &k, &n, &l, &r, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cook.cpp:16:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%d", &ss[h][i]), ss[h][i] += ss[h][i - 1];
| ~~~~~^~~~~~~~~~~~~~~~~
cook.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d", &pp[h]), pp[h]--;
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
