#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 5e3 + 7;
const int Mod = 1e9 + 7;
const int szBL = 240;
const int INF = 2e9;
const int BASE = 137;
int n, K, m, A, B;
int dp[N][N], f[N][N];
int V[N];
int T[N], S[N];
int lst[N][N];
inline void maximize (int &A, int B) { if (A < B) A = B; }
void solution () {
cin >> K >> n >> m >> A >> B;
rep (i, 1, K) cin >> V[i];
rep (i, 1, n) cin >> S[i];
rep (i, 1, m) cin >> T[i];
rep (i, 1, K)
rep (j, 1, n) {
lst[i][j] = (S[j] == i) ? j : lst[i][j - 1];
}
memset(dp, -0x3f, sizeof dp);
memset(f, -0x3f, sizeof f);
rep (j, 1, n) {
rep (i, 1, m) {
if (S[j] == T[i]) {
if (i == 1) maximize(dp[i][j], V[T[1]]);
else maximize (dp[i][j], A + B * (i - 1) + V[T[i]]);
maximize (dp[i][j], f[i - 1][j - 1] + 2 * A + B * i + B * j + V[T[i]]);
rep (k, 1, i - 1) {
if (S[j - 1] == T[k]) {
dp[i][j] = max(dp[i][j],
dp[k][j - 1] + A * (i - k >= 2) + B * (i - k - 1) + V[T[i]]);
}
}
rep (k, 1, j - 1) {
if (S[k] == T[i - 1]) {
dp[i][j] = max(dp[i][j],
dp[i - 1][k] + A * (j - k >= 2) + B * (j - k - 1) + V[T[i]]);
}
}
}
f[i][j] = max({f[i - 1][j], f[i][j - 1], dp[i][j] - B * (j + 1) - B * (i + 1)});
}
}
int res = -INF;
rep (i, 1, m)
rep (j, 1, n) res = max(res, dp[i][j] + A * (i != m) + B * (m - i));
cout << max(res, A + B * m)<<"\n";
}
#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);
/*
*/
int main () {
file("c");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
no bug challenge +2
*/
Compilation message
VisitingSingapore.cpp: In function 'int main()':
VisitingSingapore.cpp:72:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | #define file(name) freopen(name".inp", "r", stdin); \
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
VisitingSingapore.cpp:77:5: note: in expansion of macro 'file'
77 | file("c");
| ^~~~
VisitingSingapore.cpp:73:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | freopen(name".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
VisitingSingapore.cpp:77:5: note: in expansion of macro 'file'
77 | file("c");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
196692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
196660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
196692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
196692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
196692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
196732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
196692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
