Submission #1181707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181707		mehmetkagan	Visiting Singapore (NOI20_visitingsingapore)	C++20	0 / 100	12 ms	19272 KiB

VisitingSingapore

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
const int NEG = -1e15;
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int K, n, m, A, B;
    cin >> K >> n >> m >> A >> B;
    vector<int> V(K+1);
    for(int i=1;i<=K;i++) cin >> V[i];
    vector<int> S(n+1), T(m+1);
    for(int i=1;i<=n;i++) cin >> S[i];
    for(int j=1;j<=m;j++) cin >> T[j];
    vector<vector<int>> dp(m+1, vector<int>(n+1, NEG));
    for (int i = 1; i <= n; i++){
        if(S[i] == T[1])
            dp[1][i] = V[T[1]];
    }
    for (int j = 2; j <= m; j++){
        int best = NEG;
        int ptr = 1;
        for (int i = 1; i <= n; i++){
            if(S[i] == T[j-1]){
                int cand = dp[j-1][i] - i * B;
                if(cand > best) best = cand;
            }
            if(S[i] == T[j]){
                int cand1 = NEG;
                if(i > 1 && S[i-1] == T[j-1])
                    cand1 = dp[j-1][i-1];
                int cand2 = NEG;
                if(i >= 2 && best != NEG){
                    cand2 = best + A + (i - 1) * B;
                }
                dp[j][i] = V[T[j]] + max(cand1, cand2);
            }
        }
    }
    int ans = 0; for (int j = 1; j <= m; j++){
        for (int i = 1; i <= n; i++){
            if(dp[j][i] == NEG) continue;
            int pen = 0;
            if(m - j > 0) pen = A + (m - j) * B;
            ans = max(ans, dp[j][i] + pen);
        }
    }
    cout << ans << "\n";
    return 0;
}

• 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