Submission #679029

#TimeUsernameProblemLanguageResultExecution timeMemory
679029chv1Visiting Singapore (NOI20_visitingsingapore)C++14
4 / 100
45 ms87140 KiB
#include<bits/stdc++.h> using namespace std; #define int int64_t int k, n, m, a, b, v[1010], s[5050], t[5050], dp[5050][5050][2][2]; void maximize(int &a, int b) { if (a < b) a = b; } int32_t main() { // freopen("FUNTOUR.inp", "r", stdin); // freopen("FUNTOUR.inp", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 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]; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { dp[i][j][0][0] = max(dp[i][j - 1][0][0], dp[i - 1][j][0][0]) + b; dp[i][j][0][1] = dp[i - 1][j][0][1] + b; dp[i][j][1][0] = dp[i][j - 1][1][0] + b; dp[i][j][1][1] = (j == 1 ? v[t[j]] : v[t[j]] + a); if (s[i] == t[j]) { maximize(dp[i][j][1][1], dp[i - 1][j - 1][0][0] + 2 * a + v[t[j]]); maximize(dp[i][j][1][1], dp[i - 1][j - 1][0][1] + a + v[t[j]]); maximize(dp[i][j][1][1], dp[i - 1][j - 1][1][0] + a + v[t[j]]); maximize(dp[i][j][1][1], dp[i - 1][j - 1][1][1] + v[t[j]]); } } } int best = 0; for(int i = 0; i <= 1; i++) { for(int j = 0; j <= 1; j++) { maximize(best, dp[n][m][i][j]); } } cout << best; }
#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...