QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#780460#7988. 史莱姆工厂hhoppitreeWA 8ms9004kbC++171.8kb2024-11-25 11:05:512024-11-25 11:05:55

Judging History

你现在查看的是最新测评结果

  • [2024-11-25 11:05:55]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:9004kb
  • [2024-11-25 11:05:51]
  • 提交

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'