/**
* NAME : PHAM VAN SAM
* DATE : 12.01.2023 17:17:45
* ┌───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
* │Esc│ │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│ ┌┐ ┌┐ ┌┐
* └───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘ └┘ └┘ └┘
* ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
* ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │ │
* ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter │ │ 4 │ 5 │ 6 │ │
* ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤ ┌───┐ ├───┼───┼───┼───┤
* │ Shift │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│ Shift │ │ ↑ │ │ 1 │ 2 │ 3 │ │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ Win│ Alt│ Space │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │ 0 │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
**/
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define MASK(x) (1LL << (x))
#define BIT(x, k) (((x) >> (k)) & 1LL)
#define all(x) (x).begin(),(x).end()
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define Fod(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Fore(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
template <class U, class V> bool maximize(U &A, const V &B){ return (A < B) ? (A = B, true) : false;}
template <class U, class V> bool minimize(U &A, const V &B){ return (A > B) ? (A = B, true) : false;}
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }
const int MAXN = 5e3 + 5;
int N, M, K, A, B;
int v[MAXN / 5], s[MAXN], t[MAXN];
int dp[MAXN][MAXN], Max[MAXN][MAXN], Max_i[MAXN][MAXN], Max_j[MAXN][MAXN];
signed main() {
// file("TASK");
file("funtour");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> K >> N >> M >> A >> B;
For (i, 1, K) cin >> v[i];
For (i, 1, N) cin >> s[i];
For (i, 1, M) cin >> t[i];
memset(dp, -0x3f, sizeof dp);
memset(Max, -0x3f, sizeof Max);
memset(Max_i, -0x3f, sizeof Max_i);
memset(Max_j, -0x3f, sizeof Max_j);
long long ans = M * B + A;
For (i, 1, N) For (j, 1, M) {
if(s[i] == t[j]) dp[i][j] = v[s[i]] + A * (j != 1) + (j - 1) * B;
}
For (i, 1, N) For (j, 1, M) {
maximize(dp[i][j], Max[i - 1][j - 1] + (i + j) * B + 2 * A);
maximize(dp[i][j], Max_i[i][j - 1] + (i + j) * B + A);
maximize(dp[i][j], Max_j[i - 1][j] + (i + j) * B + A);
if(s[i] == t[j]) maximize(dp[i][j], dp[i - 1][j - 1] + v[s[i]]), maximize(ans, dp[i][j] + A * (j != M) + (M - j) * B);
maximize(Max[i][j], max(Max[i - 1][j], Max[i][j - 1]));
maximize(Max[i][j], dp[i][j] - (i + j) * B);
maximize(Max_i[i][j], dp[i][j] - (i + j) * B);maximize(Max_i[i][j], Max_i[i][j - 1]);
maximize(Max_j[i][j], dp[i][j] - (i + j) * B);maximize(Max_j[i][j], Max_j[i - 1][j]);
}
cout << ans;
// cerr << "Time elapsed: " << TIME << " s.\n";
return (0 ^ 0);
}
/*
Max[i][j] = max(dp[x][y]) x <= i && y <= j
Max_i[i][j] = max(dp[i][y]) y <= j
Max_j[i][j] = max(dp[x][j]) x <= i
*/
/*
A + (q - p + 1) * B
A + q * B - (p - 1) * B
*/
Compilation message
VisitingSingapore.cpp: In function 'int main()':
VisitingSingapore.cpp:30:56: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
VisitingSingapore.cpp:45:5: note: in expansion of macro 'file'
45 | file("funtour");
| ^~~~
VisitingSingapore.cpp:30:89: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
VisitingSingapore.cpp:45:5: note: in expansion of macro 'file'
45 | file("funtour");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
100 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
103 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
102 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
100 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
