| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 920641 |
2024-02-02T20:05:38 Z |
rainboy |
None (KOI17_cook) |
C++17 |
|
2 ms |
10844 KB |
/* https://oj.uz/submission/366848 (leinad2) */
/* used solution to find bugs */
#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], dq[K][N], qu[K][N], 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]--;
ans = INF;
for (i = 0; i < n; i++) {
h1 = h2 = h3 = -1;
for (h = 0; h < k; h++) {
if (i >= l && dq[h][i - l] != INF) {
while (cnt[h] && dq[h][qu[h][head[h] + cnt[h] - 1]] >= dq[h][i - l])
cnt[h]--;
qu[h][head[h] + cnt[h]++] = i - l;
}
if (cnt[h] && qu[h][head[h]] == i - r - 1)
head[h]++, cnt[h]--;
dp[h][i] = i == 0 ? 0 : (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;
if (n - i <= r)
ans = min(ans, dp[h_][i] + ss[h][n] - ss[h][i]);
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
cook.cpp: In function 'int main()':
cook.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | scanf("%d%d%d%d%d", &k, &n, &l, &r, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cook.cpp:18:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d", &ss[h][i]), ss[h][i] += ss[h][i - 1];
| ~~~~~^~~~~~~~~~~~~~~~~
cook.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%d", &pp[h]), pp[h]--;
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
