QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#780460 | #7988. 史莱姆工厂 | hhoppitree | WA | 8ms | 9004kb | C++17 | 1.8kb | 2024-11-25 11:05:51 | 2024-11-25 11:05:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 155, M = 15;
int c[N], w[N], p[N];
long long f[N][N], fl[N][N][M], fr[N][N][M];
void upd(long long &x, long long y) {
(y > x) && (x = y);
}
signed main() {
int n, m, t; scanf("%d%d%d", &n, &m, &t);
for (int i = 1; i <= n; ++i) scanf("%d", &c[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
for (int i = m; i <= m * 2 - 2; ++i) scanf("%d", &p[i]);
for (int i = m - 1; i; --i) p[i] = p[i + 1] - t;
memset(f, -0x3f, sizeof(f)), memset(fl, -0x3f, sizeof(f)), memset(fr, -0x3f, sizeof(f));
for (int i = 1; i <= n; ++i) fl[i][i][w[i]] = fr[i][i][w[i]] = f[i][i - 1] = 0, f[i][i] = p[w[i]];
for (int l = n; l >= 1; --l) {
for (int r = l + 1; r <= n; ++r) {
fl[l][r][w[l]] = f[l + 1][r];
for (int i = l + 1; i <= r; ++i) {
if (c[i] != c[l]) continue;
for (int j = 1; j + w[l] < m; ++j) upd(fl[l][r][j + w[l]], fl[i][r][j] + f[l + 1][i - 1]);
}
fr[l][r][w[r]] = f[l][r - 1];
for (int i = l; i <= r - 1; ++i) {
if (c[i] != c[r]) continue;
for (int j = 1; j + w[r] < m; ++j) upd(fr[l][r][j + w[r]], fr[l][i][j] + f[i + 1][r - 1]);
}
for (int i = l; i < r; ++i) {
if (c[l - 1] != c[i + 1] || c[r + 1] != c[i]) upd(f[l][r], f[l][i] + f[i + 1][r]);
}
if (c[l] != c[r]) continue;
for (int i = l; i < r; ++i) {
for (int j = 1; j < m; ++j) {
for (int k = 1; k < m; ++k) {
upd(f[l][r], fl[l][i][j] + fr[i + 1][r][k] + p[j + k]);
}
}
}
}
}
printf("%lld\n", f[1][n]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6364kb
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: 0
Accepted
time: 1ms
memory: 8412kb
input:
5 7 500 2 3 2 3 2 5 6 6 6 4 1000 900 800 400 200 50
output:
1400
result:
ok single line: '1400'
Test #3:
score: -100
Wrong Answer
time: 8ms
memory: 9004kb
input:
150 10 465782 6 1 4 3 2 6 1 3 5 3 4 6 1 2 1 5 1 6 2 1 5 4 6 1 3 2 6 5 4 3 1 6 3 4 1 4 1 6 3 6 1 4 2 4 6 4 3 1 5 6 4 2 1 4 6 2 5 1 3 1 4 6 5 6 3 2 3 4 2 3 6 3 5 2 6 1 5 4 5 2 4 1 4 3 4 1 3 2 6 1 4 5 4 6 2 1 3 1 2 1 3 5 2 3 2 6 5 3 1 4 1 5 1 6 2 5 4 2 4 1 4 2 5 6 4 3 5 1 3 2 5 4 6 4 3 5 3 4 5 3 2 1 4 ...
output:
457439170
result:
wrong answer 1st lines differ - expected: '392867316', found: '457439170'