Submission #1214700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214700		VMaksimoski008	Visiting Singapore (NOI20_visitingsingapore)	C++20	4 / 100	141 ms	327680 KiB

VisitingSingapore

#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';
}

• 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