Submission #340398

#	Time	Username	Problem	Language	Result	Execution time	Memory
340398		apostoldaniel854	Visiting Singapore (NOI20_visitingsingapore)	C++14	100 / 100	1061 ms	748 KiB

VisitingSingapore

#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;
}

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 12 / 12
• Subtask 4: 7 / 7
• Subtask 5: 8 / 8
• Subtask 6: 13 / 13
• Subtask 7: 50 / 50