QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#780894#7988. 史莱姆工厂hhoppitreeWA 1ms6340kbC++171.8kb2024-11-25 13:53:122024-11-25 13:53:13

Judging History

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

  • [2024-11-25 13:53:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6340kb
  • [2024-11-25 13:53:12]
  • 提交

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][N], fr[N][N][N];

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 + 1; ++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: 0
Wrong Answer
time: 1ms
memory: 6340kb

input:

4 5 6
2 1 2 3
3 3 3 4
5 7 9 11

output:

10

result:

wrong answer 1st lines differ - expected: '-1', found: '10'