Submission #1214700

#TimeUsernameProblemLanguageResultExecution timeMemory
1214700VMaksimoski008Visiting Singapore (NOI20_visitingsingapore)C++20
4 / 100
141 ms327680 KiB
#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 5005;

ll dp[N][N], dp2[N][N];
int n, m, K, A, B, V[N], T[N], S[N];

signed main() {
    cin >> K >> n >> m >> A >> B;
    for(int i=1; i<=K; i++) cin >> V[i];
    for(int i=1; i<=n; i++) cin >> S[i];
    for(int i=1; i<=m; i++) cin >> T[i];

    ll ans = A + m * B;
    for(int i=0; i<=n; i++)
        for(int j=0; j<=m; j++)
            dp[i][j] = dp2[i][j] = -1e18;

    dp[0][0] = 0;
    for(int i=0; i<=n; i++) {
        for(int j=0; j<=m; j++) {
            if(i) dp[i][j] = max(dp[i][j], dp[i-1][j] + B);
            if(j) dp[i][j] = max(dp[i][j], dp[i][j-1] + B);
            if(i && j && S[i] == T[j]) {
                dp2[i][j] = max(dp[i-1][j-1], ll(j-1) * B) + V[S[i]];
                dp[i][j] = max(dp[i][j], dp2[i][j]);
                ans = max(ans, dp2[i][j] + (m - j) * B);
            }
        }
    }
    cout << ans << '\n';
}
#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...