제출 #1181707

#제출 시각아이디문제언어결과실행 시간메모리
1181707mehmetkaganVisiting Singapore (NOI20_visitingsingapore)C++20
0 / 100
12 ms19272 KiB
#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;
}
#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...