#include <iostream>
#include <algorithm>
#include<assert.h>
using namespace std;
int n, a[10001], dp[4][10001], dp2[4][10001];
inline int get_type(int a1, int a2, int a3) {
int min3 = min(a1, min(a2, a3));
if (
(min3 == a1 && min3 == a2 && min3 == a3) ||
(min3 != a1 && min3 == a2 && min3 != a3) ||
(min3 != a1 && min3 != a2 && min3 == a3) ||
(min3 == a1 && min3 == a2 && min3 != a3) ||
(min3 != a1 && min3 == a2 && min3 == a3) )
return 1;
else
return 2;
}
inline pair<int, int> get_t1cost(int a1, int a2, int a3) {
int cost = 0;
int c3 = min(a1, min(a2, a3));
a1 -= c3;
a2 -= c3;
a3 -= c3;
cost += 7 * c3;
int c2 = min(a1, a2);
a1 -= c2;
a2 -= c2;
cost += 5 * c2;
int c1 = a1 + a2;
a1 = 0;
a2 = 0;
cost += 3 * c1;
return {cost, a3};
}
int main(void) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
a[n] = 0;
for (int i = n - 1; i >= max(0, n - 2); i--) {
for (int j = a[i]; j >= 0; j--) {
int i0 = i % 4;
auto t = get_t1cost(j, a[i + 1], 0);
dp[i0][j] = t.first;
dp2[i0][j] = t.first - j * 2;
if (j + 1 <= a[i])
dp2[i0][j] = min(dp2[i0][j], dp2[i0][j + 1]);
}
}
for (int i = n - 3; i >= 0; i--) {
int i0 = i % 4, i1 = (i + 1) % 4, i2 = (i + 2) % 4, i3 = (i + 3) % 4;
for (int j = a[i]; j >= 0; j--) {
int a1 = j, a2 = a[i + 1], a3 = a[i + 2], a4 = a[i + 3];
int cost;
//printf("---- %d %d ----\n", i, j);
if (get_type(a1, a2, a3) == 1 || a4 == 0) {
auto t = get_t1cost(a1, a2, a3);
cost = t.first + dp[i2][t.second];
//printf("type 1");
//printf("t.first %d cost %d\n", t.first, cost);
}
else {
cost = 0;
cost += (2 * a1 + 3 * a2 + 4 * a3);
cost += dp2[i3][max(0, max(a4 - a3, a1 - a2 + a4))];
cost += 2 * (a4 - a3);
//printf("type 2\n");
//printf("dp2 %d %d cost %d\n", max(0, max(a4 - a3, a1 - a2 + a4)), dp2[i + 3][max(0, max(a4 - a3, a1 - a2 + a4))], cost);
}
dp[i0][j] = cost;
dp2[i0][j] = cost - j * 2;
if (j + 1 <= a[i])
dp2[i0][j] = min(dp2[i0][j], dp2[i0][j + 1]);
//printf("\n");
}
}
printf("%d\n", dp[0 % 4][a[0]]);
//system("pause");
return 0;
}
Compilation message
skyline.cpp: In function 'int main()':
skyline.cpp:65:25: warning: unused variable 'i1' [-Wunused-variable]
65 | int i0 = i % 4, i1 = (i + 1) % 4, i2 = (i + 2) % 4, i3 = (i + 3) % 4;
| ^~
skyline.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
skyline.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
