#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int inf = 1e9;
int main(){
int k,n,m,a,b;
cin >> k >> n >> m >> a >> b;
a *= -1;
b *= -1;
vector<int> v(k + 1),s(n + 1),t(m + 1);
for(int i = 1;i <= k;i++){
cin >> v[i];
}
vector<vector<int>> hs(k + 1);
for(int i = 1;i <= n;i++){
cin >> s[i];
hs[s[i]].push_back(i);
}
for(int i = 1;i <= m;i++){
cin >> t[i];
}
// int dp[m + 5][n + 5][3];
// vector<vector<vector<int>>> dp(m + 5,vector<vector<int>>(n + 5,vector<int>(3,-inf)));
/*
dp[i][j][x] -> max happiness if start at day i and at index j(on t)
x = 0 -> no behind in t
x = 1 -> just behind in t
x = 2 -> far behind in t
*/
// for(int i = 0;i <= n + 4;i++){
// for(int j = 0;j <= m + 4;j++){
// for(int x = 0;x <= 2;x++){
// dp[i][j][x] = -inf;
// }
// }
// }
vector<vector<int>> dp(n + 4,vector<int>(3,-inf));
vector<vector<int>> ndp(n + 4,vector<int>(3,-inf));
vector<vector<int>> ndp2(n + 4,vector<int>(3,-inf));
int ans = -m * b - a;
for(int j = m;j >= 1;j--){
for(int i = n;i >= 1;i--){
for(int x = 0;x <= 2;x++){
int tot = -inf;
// attend t[i]
for(int e : hs[t[j]]){
if(e < i) continue;
// taking eth day
// int sub = (e - i) * b + ((e > i) ? a : 0);
// tot = max(tot,dp[j + 1][e + 1][1] - sub + v[t[j]]);
// tot = max(tot,dp[j + 2][e + 1][2] - sub + v[t[j]] + (j + 1) * b - a);
// // leave at eth day
// tot = max(tot,v[t[j]] - sub - (m - j) * b - ((m > j) ? a : 0));
int sub = (e - i) * b + ((e > i) ? a : 0);
tot = max(tot,ndp[e + 1][1] - sub + v[t[j]]);
tot = max(tot,ndp2[e + 1][2] - sub + v[t[j]] + (j + 1) * b - a);
// leave at eth day
tot = max(tot,v[t[j]] - sub - (m - j) * b - ((m > j) ? a : 0));
}
if(x == 2){
tot -= j * b;
}
// skip t[j]
if(x == 2) tot = max(tot,ndp[i][2]);
dp[i][x] = tot;
// cout << i << " " << j << " " << x << " : " << tot << '\n';
}
ans = max(ans,dp[i][0] - (j - 1) * b - ((j > 1) ? a : 0));
}
ndp2 = ndp;
ndp = dp;
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |