oj.uz

Submission #478208

# Submission time Handle Problem Language Result Execution time Memory
478208 2021-10-06T13:16:59 Z blue Visiting Singapore (NOI20_visitingsingapore) C++17
0 / 100
 29 ms 38236 KB 
#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] = -INF;
    for(int j = 0; j <= M; j++) DP[0][j] = DP_max[0][j] = -INF;

    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) + (j == 1 ? 0 : A + (j-1)*B);
                if(i-2 >= 0) DP[i][j] = max(DP[i][j], DP_max[i-2][j-1] - (A+B) + V_new[S[i]]);
                if(j-2 >= 0) DP[i][j] = max(DP[i][j], DP_max[i-1][j-2] - (A+B) + V_new[S[i]]);
                if(i-2 >= 0 && j-2 >= 0) DP[i][j] = max(DP[i][j], DP_max[i-2][j-2] + V_new[S[i]]);
                DP[i][j] = max(DP[i][j], DP_max[i-1][j-1] - 2*(B));

// if(i == 2 && j == 2) cerr << V[S[i]] - B*(i+j) + B*(i+j) << ' ' << DP_max[i-2][j-1] - (A+B) + V_new[S[i]] + B*(i+j) << ' ' <<  DP_max[i-1][j-2] - (A+B) + V_new[S[i]] + B*(i+j) << ' ' << DP_max[i-2][j-2] + V_new[S[i]] + B*(i+j) << ' ' << DP_max[i-1][j-1] - 2*(A+B) + B*(i+j) << '\n';

                // 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 << ' ' << DP[i][j] + B*(i+j) << '\n';

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

            ans = max(ans, DP[i][j] + B*(i+j) + (j == M ? 0 : A + (M-j)*B));

            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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 38236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 38236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 38236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -