QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#353408 | #7988. 史莱姆工厂 | alpha1022 | WA | 1ms | 5052kb | C++14 | 1.5kb | 2024-03-14 08:28:48 | 2024-03-14 08:28:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 150;
const int M = 10;
int n, m, w;
int c[N + 5], a[N + 5], p[M];
int f[N + 5][N + 5], g[N + 5][N + 5], h[N + 5][N + 5][M];
int main() {
scanf("%d%d%d", &n, &m, &w);
for (int i = 1; i <= n; ++i) scanf("%d", c + i);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
for (int i = 0; i < m - 1; ++i) scanf("%d", p + i);
memset(f, -0x3f, sizeof f), memset(g, -0x3f, sizeof g), memset(h, -0x3f, sizeof h);
for (int i = 0; i <= n; ++i) f[i + 1][i] = 0;
for (int l = n; l; --l)
for (int r = l; r <= n; ++r) {
if (c[r] != c[r + 1]) {
h[l][r][a[r]] = f[l][r - 1];
for (int k = l; k + 1 < r; ++k)
if (c[k] == c[r])
for (int i = a[r]; i < m; ++i)
h[l][r][i] = max(h[l][r][i], h[l][k][i - a[r]] + f[k + 1][r - 1]);
for (int i = a[r]; i < m; ++i) g[l][r] = max(g[l][r], h[l][r][i] - w * (m - i) + p[0]);
for (int k = l; k + 1 < r; ++k)
if (c[k] == c[r])
for (int i = a[k]; i < m; ++i)
for (int j = max(a[r], m - i); j < m; ++j)
g[l][r] = max(g[l][r], h[l][k][i] + h[k + 1][r][j] + p[i + j - m]);
}
for (int k = l; k <= r; ++k)
if (c[k] != c[r + 1])
for (int i = 0; i < m * 2 - 1; ++i)
f[l][r] = max(f[l][r], g[l][k] + f[k + 1][r]);
}
printf("%d\n", f[1][n]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5052kb
input:
4 5 6 2 1 2 3 3 3 3 4 5 7 9 11
output:
-1
result:
ok single line: '-1'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 4956kb
input:
5 7 500 2 3 2 3 2 5 6 6 6 4 1000 900 800 400 200 50
output:
2300
result:
wrong answer 1st lines differ - expected: '1400', found: '2300'