Submission #340398

#TimeUsernameProblemLanguageResultExecution timeMemory
340398apostoldaniel854Visiting Singapore (NOI20_visitingsingapore)C++14
100 / 100
1061 ms748 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int MAX_N = 5000, INF = 1e9;
int dp[2][1 + MAX_N][2][2];
int V[1 + MAX_N];
int S[1 + MAX_N];
int T[1 + MAX_N];
int K, A, B, n, m;

void upd (int &a, int b) {
    if (a < b)
        a = b;
}

void recurence (int i, int j, int bi, int bj) {
    if (i < n && j < m && S[i + 1] == T[j + 1])
        upd (dp[1 - (i & 1)][j + 1][0][0], dp[i & 1][j][bi][bj] + V[S[i + 1]]);
    if (i < n)
        upd (dp[1 - (i & 1)][j][1][bj], dp[i & 1][j][bi][bj] + B + ((bi == 0) ? A : 0));
    if (j < m)
        upd (dp[i & 1][j + 1][bi][1], dp[i & 1][j][bi][bj] + B + ((bj == 0) ? A : 0));
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    cin >> K >> n >> m >> A >> B;
    for (int i = 1; i <= K; i++)
        cin >> V[i];
    for (int i = 1; i <= n; i++)
        cin >> S[i];
    for (int i = 1; i <= m; i++)
        cin >> T[i];
    for (int j = 0; j <= m; j++)
        for (int bi = 0; bi < 2; bi++)
            for (int bj = 0; bj < 2; bj++)
                dp[0][j][bi][bj] = -INF;
    dp[0][0][0][0] = 0;
    int ans = A + m * B;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++)
            for (int bi = 0; bi < 2; bi++)
                for (int bj = 0; bj < 2; bj++)
                    dp[1 - (i & 1)][j][bi][bj] = -INF;
        dp[1 - (i & 1)][0][0][0] = 0;
        for (int j = 0; j <= m; j++)
            for (int bi = 0; bi < 2; bi++)
                for (int bj = 0; bj < 2; bj++)
                    if (dp[i & 1][j][bi][bj] != -INF)
                        recurence (i, j, bi, bj);
        for (int bi = 0; bi < 2; bi++)
            for (int bj = 0; bj < 2; bj++)
                upd (ans, dp[i & 1][m][bi][bj]);
    }
    cout << ans << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...