제출 #1181713

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181713		mehmetkagan	Visiting Singapore (NOI20_visitingsingapore)	C++20	4 / 100	109 ms	193572 KiB

VisitingSingapore

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
const int NEG = -1000000000000000000LL;
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>> M(n+1, vector<int>(m+1, NEG));
    vector<vector<int>> I(n+1, vector<int>(m+1, NEG));
    vector<vector<int>> D(n+1, vector<int>(m+1, NEG));
    for (int i = 0; i <= n; i++){
        I[i][0] = 0;
        M[i][0] = NEG;
        D[i][0] = NEG;
    }
    for (int j = 1; j <= m; j++){
        M[0][j] = NEG;
        I[0][j] = NEG;
        D[0][j] = NEG;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if(S[i] == T[j]){
                int cand = max({M[i-1][j-1], I[i-1][j-1], D[i-1][j-1]});
                if(j == 1) cand = max(cand, (int)0);
                if(cand != NEG) 
                    M[i][j] = cand + V[T[j]];
            }
            int candI1 = I[i-1][j] + B;
            int candI2 = M[i-1][j] + A + B;
            int candI3 = D[i-1][j] + A + B;
            I[i][j] = max({candI1, candI2, candI3});
            int candD1 = D[i][j-1] + B;
            int candD2 = M[i][j-1] + A + B;
            int candD3 = I[i][j-1] + A + B;
            D[i][j] = max({candD1, candD2, candD3});
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++){
        ans = max(ans, max({M[i][m], I[i][m], D[i][m]}));
    }
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 4 / 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