QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #188661 | #1093. Bookcase Solidity United | FISHER_ | WA | 2ms | 7292kb | C++14 | 792b | 2023-09-26 10:27:11 | 2023-09-26 10:27:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 70, V = 150;
int a[maxn + 5];
int f[maxn + 5][maxn + 5][V + 5];
inline void upd(int& x, int y) { x = min(x, y); }
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
memset(f, 63, sizeof(f));
for (int i = 1; i <= n; i++) f[i][i][a[i] / 2] = a[i];
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
for (int x = 0; x <= V; x++) {
upd(f[i][j][max(a[j], x) / 2], f[i][j - 1][x] + max(a[j] - x, 0));
for (int k = i; k < j; k++)
for (int y = 0; y <= x; y++) upd(f[i][j][x], f[i][k][y] + f[k + 1][j][x - y]);
}
for (int i = 1; i <= n; i++) {
int ans = 1E9;
for (int j = 0; j <= V; j++) upd(ans, f[1][i][j]);
printf("%d ", ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7288kb
input:
3 8 1 2
output:
8 8 8
result:
ok 3 number(s): "8 8 8"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7284kb
input:
5 10 3 3 8 4
output:
10 10 11 17 17
result:
ok 5 number(s): "10 10 11 17 17"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7164kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 7172kb
input:
1 150
output:
150
result:
ok 1 number(s): "150"
Test #5:
score: 0
Accepted
time: 2ms
memory: 7236kb
input:
2 80 82
output:
80 122
result:
ok 2 number(s): "80 122"
Test #6:
score: 0
Accepted
time: 1ms
memory: 7292kb
input:
2 4 76
output:
4 78
result:
ok 2 number(s): "4 78"
Test #7:
score: 0
Accepted
time: 0ms
memory: 7268kb
input:
2 32 124
output:
32 140
result:
ok 2 number(s): "32 140"
Test #8:
score: 0
Accepted
time: 1ms
memory: 7284kb
input:
2 2 119
output:
2 120
result:
ok 2 number(s): "2 120"
Test #9:
score: 0
Accepted
time: 1ms
memory: 7228kb
input:
5 4 82 94 39 20
output:
4 84 137 137 137
result:
ok 5 number(s): "4 84 137 137 137"
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 7292kb
input:
7 85 49 150 12 50 94 113
output:
85 92 218 218 230 280 340
result:
wrong answer 6th numbers differ - expected: '274', found: '280'