Submission #478204

#	Time	Username	Problem	Language	Result	Execution time	Memory
478204		blue	Visiting Singapore (NOI20_visitingsingapore)	C++17	0 / 100	29 ms	38140 KiB

VisitingSingapore

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const long long INF = 1'000'000'000'000'000'000LL;

int main()
{
    int K, N, M;
    long long A, B;
    cin >> K >> N >> M >> A >> B;

    long long V_new[1+K];
    long long V[1+K];
    for(int k = 1; k <= K; k++)
    {
        cin >> V[k];
        V_new[k] = V[k] + 2*(A-B);
    }

    long long ans = 0;

    long long S[1+N], T[1+M];
    for(int i = 1; i <= N; i++) cin >> S[i];
    for(int j = 1; j <= M; j++) cin >> T[j];

    long long* DP[1+N];
    long long* DP_max[1+N];

    DP[0] = new long long[1+M];
    DP[1] = new long long[1+M];
    DP_max[0] = new long long[1+M];
    DP_max[1] = new long long[1+M];
    for(int i = 2; i <= N; i++)
    {
        // DP[i] = DP[i-2];
        // DP_max[i] = DP_max[i-2];
        DP[i] = new long long[1+M];
        DP_max[i] = new long long[1+M];
    }

    // for(int k = 1; k <= K; k++) cerr << V_new[k] << ' ';
    // cerr << '\n';

    cerr << "v new = " << V_new[1] << '\n';




    for(int i = 0; i <= N; i++) DP[i][0] = DP_max[i][0] = 0;
    for(int j = 0; j <= M; j++) DP[0][j] = DP_max[0][j] = 0;

    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            if(S[i] != T[j]) DP[i][j] = -INF;
            else
            {
                DP[i][j] = V[S[i]] - B*(i+j);
                if(i-2 >= 0) DP[i][j] = max(DP[i][j], DP_max[i-2][j-1] - (A+B) + V[S[i]]);
                if(j-2 >= 0) DP[i][j] = max(DP[i][j], DP_max[i-1][j-2] - (A+B) + V[S[i]]);
                if(i-2 >= 0 && j-2 >= 0) DP[i][j] = max(DP[i][j], DP_max[i-2][j-2] + V[S[i]]);
                DP[i][j] = max(DP[i][j], DP_max[i-1][j-1] - 2*(A+B));

                // DP[i][j] = max({V[ S[i] ] - B*(i+j),
                //                 DP_max[i-2][j-1] - A - B + V[S[i]],
                //                 DP_max[i-1][j-2] - A - B + V[S[i]],
                //                 DP_max[i-2][j-2] + V[S[i]],
                //                 DP_max[i-1][j-1] - 2*(A+B)});
                // DP[i][j] = max({V[ S[i] ] - B*(i+j), DP_max[i-1][j-1] + V_new[ S[i] ]});
            }

            // cerr << i << ' ' << j << ": " << V[ S[i] ] - B*(i+j) << ' ' << DP_max[i-1][j-1] << "+" << V_new[ S[i] ] << ' ';

            // cerr << DP[i][j] << " \n";

            ans = max(ans, DP[i][j] + B*(i+j));

            DP_max[i][j] = max({DP_max[i-1][j], DP_max[i][j-1], DP[i][j]});
        }
        // cerr << '\n';
    }

    cout << ans << '\n';
}

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