#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 3000;
int n, t,s1[MAX_N+1],s2[MAX_N+1],dp[MAX_N+1];
int u[MAX_N + 1], v[MAX_N + 1], d[MAX_N + 1], e[MAX_N + 1];
int main() {
scanf("%d %d", &n, &t);
for (int i = 1; i <= n; i++) {
scanf("%d %d %d %d", &u[i], &v[i], &d[i], &e[i]);
s1[i] = s1[i - 1] + u[i] + v[i];
s2[i] = s2[i - 1] + min(u[i] + v[i], d[i] + e[i]);
}
fill(dp + 1, dp + 1 + n, 1e9);
int mini = 1e9;
for (int i = 0; i <n; i++) {
if(i) mini = min(mini, v[i] + d[i] - 2 * i*t);
for (int j = i + 1; j <= n; j++) {
dp[j] = min({ dp[j],
dp[i] + s1[j] - s1[i] + (j - i)*t,
dp[i] + (3 * j - i)*t + s2[j - 1] - s2[i] + u[j] + e[j] +mini });
if (j != i + 1) dp[j] = min(dp[j],
dp[i] + (3 * j - 3 * i - 2)*t + s2[j - 1] - s2[i + 1] + u[j] + e[j] + v[i + 1] + d[i + 1]);
}
}
printf("%d", dp[n] + t);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1164 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1164 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
42 ms |
1164 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1164 KB |
Output is correct |
| 3 |
Correct |
42 ms |
1164 KB |
Output is correct |
| 4 |
Correct |
33 ms |
1164 KB |
Output is correct |
| 5 |
Correct |
25 ms |
1164 KB |
Output is correct |
| 6 |
Incorrect |
11 ms |
1164 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
