#include <iostream>
using namespace std;
const int INF = 1e9;
const int KMAX = 1000;
const int NMAX = 5000;
int K, N, M, A, B;
int dp[2][NMAX + 5][2][2];
int v[KMAX + 5], s[NMAX + 5], t[NMAX + 5];
int main()
{
cin >> K >> N >> M >> A >> B;
A = -A;
B = -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 = 0; i < 2; i++)
for(int j = 0; j <= M; j++)
for(int x = 0; x < 2; x++)
for(int y = 0; y < 2; y++)
dp[i][j][x][y] = -INF;
dp[0][0][0][0] = 0;
int res = A + M * B;
for(int i = 1; i <= N; i++)
{
for(int j = 0; j <= M - 1; j++)
{
///Skip concert
dp[0][j + 1][0][1] = max(dp[0][j + 1][0][1], dp[0][j][0][0] - A - B);
dp[0][j + 1][0][1] = max(dp[0][j + 1][0][1], dp[0][j][0][1] - B);
dp[0][j + 1][1][1] = max(dp[0][j + 1][1][1], dp[0][j][1][0] - A - B);
dp[0][j + 1][1][1] = max(dp[0][j + 1][1][1], dp[0][j][1][1] - B);
///Skip day
dp[1][j][1][0] = max(dp[1][j][1][0], dp[0][j][0][0] - A - B);
dp[1][j][1][0] = max(dp[1][j][1][0], dp[0][j][1][0] - B);
dp[1][j][1][1] = max(dp[1][j][1][1], dp[0][j][0][1] - A - B);
dp[1][j][1][1] = max(dp[1][j][1][1], dp[0][j][1][1] - B);
///Attend
if(s[i] == t[j + 1])
{
dp[1][j + 1][0][0] = max(dp[1][j + 1][0][0], dp[0][j][0][0] + v[t[j + 1]]);
dp[1][j + 1][0][0] = max(dp[1][j + 1][0][0], dp[0][j][1][0] + v[t[j + 1]]);
dp[1][j + 1][0][0] = max(dp[1][j + 1][0][0], dp[0][j][0][1] + v[t[j + 1]]);
dp[1][j + 1][0][0] = max(dp[1][j + 1][0][0], dp[0][j][1][1] + v[t[j + 1]]);
}
}
res = max(res, dp[0][M][0][0]);
res = max(res, dp[0][M][0][1]);
res = max(res, dp[0][M][1][0]);
res = max(res, dp[0][M][1][1]);
res = max(res, dp[1][M][0][0]);
res = max(res, dp[1][M][0][1]);
res = max(res, dp[1][M][1][0]);
res = max(res, dp[1][M][1][1]);
for(int j = 0; j <= M; j++)
for(int x = 0; x < 2; x++)
for(int y = 0; y < 2; y++)
{
dp[0][j][x][y] = dp[1][j][x][y];
dp[1][j][x][y] = -INF;
}
}
cout << res << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
12 ms |
428 KB |
Output is correct |
3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
364 KB |
Output is correct |
2 |
Correct |
10 ms |
364 KB |
Output is correct |
3 |
Correct |
84 ms |
492 KB |
Output is correct |
4 |
Correct |
204 ms |
620 KB |
Output is correct |
5 |
Incorrect |
58 ms |
620 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
364 KB |
Output is correct |
2 |
Correct |
10 ms |
364 KB |
Output is correct |
3 |
Correct |
84 ms |
492 KB |
Output is correct |
4 |
Correct |
204 ms |
620 KB |
Output is correct |
5 |
Incorrect |
58 ms |
620 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
364 KB |
Output is correct |
2 |
Correct |
10 ms |
364 KB |
Output is correct |
3 |
Correct |
84 ms |
492 KB |
Output is correct |
4 |
Correct |
204 ms |
620 KB |
Output is correct |
5 |
Incorrect |
58 ms |
620 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
12 ms |
428 KB |
Output is correct |
3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |