oj.uz

Submission #691638

# Submission time Handle Problem Language Result Execution time Memory
691638 2023-01-31T11:04:33 Z penguin133 Visiting Singapore (NOI20_visitingsingapore) C++17
16 / 100
 176 ms 196192 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif

int S[5005], T[5005], V[5005], memo[5005][5005][2][2], n, m, k, a, b;
/*
int dp(int x, int y, bool f, bool f2){
	if(y == m + 1)return 0;
	if(x == n + 1)return b * (m - y + 1) + (!f2 ? a : 0);
	if(memo[x][y][f][f2] != -1)return memo[x][y][f][f2];
	int res = max(dp(x+1, y, 1, f2) + b + (!f ? a : 0), dp(x, y+1, f, 1) + b + (!f2 ? a : 0));
	if(S[x] == T[y])res = max(res, dp(x+1, y+1, 0, 0) + V[S[x]]);
	return memo[x][y][f][f2] = res;
}
*/
int dp[5005][5005][2][2];
int dp2[5005][5005];
void solve(){
	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];
	/*
	memset(memo, -1, sizeof(memo));
	int res = -1e18;
	for(int i=1;i<=n;i++)res = max(res, dp(i, 1, 0, 0));
	cout << res;
	*/
	int res = -1e18;
	for(int i=0;i<=m;i++)dp[0][i][0][0] = dp[0][i][1][1] = dp[0][i][1][0] = dp[0][i][0][1] = -1e18;
	/*
	dp[0][0][0][0] = 0;
	for(int i=1;i<=n;i++){
		int x = i&1;
		dp[x][0][0][0] = 0;
		dp[x][0][0][1] = dp[x][0][1][0] = dp[x][0][1][1] = -1e18;
		for(int j=1;j<=m;j++){
			dp[x][j][0][0] = (S[i] == T[j] ? max({dp[1-x][j-1][0][0], dp[1-x][j-1][0][1], dp[1-x][j-1][1][0], dp[1-x][j-1][1][1]}) + V[S[i]] : (int)-1e18);
			dp[x][j][0][1] = max(dp[x][j-1][0][0] + a + b, dp[x][j-1][0][1] + b);
			dp[x][j][1][0] = max(dp[1-x][j][0][0] + a + b, dp[1-x][j][1][0] + b);
			dp[x][j][1][1] = max({
								dp[1-x][j-1][0][0] + a * 2 + b * 2,
								dp[1-x][j-1][0][1] + a + b * 2,
								dp[1-x][j-1][1][0] + a + b * 2,
								dp[1-x][j-1][1][1] + b * 2
								});
			res = max(res, dp[x][j][0][0] + (m - j) * b + (m == j ? 0 : a));
			res = max(res, dp[x][j][1][0] + (m - j) * b + (m == j ? 0 : a));
			res = max(res, dp[x][j][0][1] + (m - j) * b);
			res = max(res, dp[x][j][1][1] + (m - j) * b);
		}
	}
	*/
	for(int i=1;i<=n;i++){
		int x = i & 1;
		for(int j=1;j<=m;j++){
			if(S[i] == T[j])dp2[i][j] = dp2[i-1][j-1] + V[S[i]];
			else dp2[i][j] = max(dp2[i-1][j], dp2[i][j-1]);
			res = max(res, dp2[i][j]);
		}
	}
	cout << res;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

VisitingSingapore.cpp: In function 'void solve()':
VisitingSingapore.cpp:63:7: warning: unused variable 'x' [-Wunused-variable]
   63 |   int x = i & 1;
      |       ^
VisitingSingapore.cpp: At global scope:
VisitingSingapore.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main(){
      | ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 6 ms 10836 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 3 ms 3924 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 5 ms 7252 KB Output is correct
10 Correct 9 ms 12224 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29948 KB Output is correct
2 Correct 18 ms 18172 KB Output is correct
3 Correct 73 ms 79904 KB Output is correct
4 Correct 176 ms 174388 KB Output is correct
5 Correct 45 ms 51564 KB Output is correct
6 Correct 64 ms 76404 KB Output is correct
7 Correct 114 ms 143564 KB Output is correct
8 Correct 56 ms 54840 KB Output is correct
9 Correct 74 ms 91588 KB Output is correct
10 Correct 168 ms 196172 KB Output is correct
11 Correct 161 ms 195748 KB Output is correct
12 Correct 167 ms 196192 KB Output is correct
13 Correct 168 ms 196124 KB Output is correct
14 Correct 102 ms 196168 KB Output is correct
15 Correct 112 ms 196176 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29948 KB Output is correct
2 Correct 18 ms 18172 KB Output is correct
3 Correct 73 ms 79904 KB Output is correct
4 Correct 176 ms 174388 KB Output is correct
5 Correct 45 ms 51564 KB Output is correct
6 Correct 64 ms 76404 KB Output is correct
7 Correct 114 ms 143564 KB Output is correct
8 Correct 56 ms 54840 KB Output is correct
9 Correct 74 ms 91588 KB Output is correct
10 Correct 168 ms 196172 KB Output is correct
11 Correct 161 ms 195748 KB Output is correct
12 Correct 167 ms 196192 KB Output is correct
13 Correct 168 ms 196124 KB Output is correct
14 Correct 102 ms 196168 KB Output is correct
15 Correct 112 ms 196176 KB Output is correct
16 Incorrect 114 ms 117784 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29948 KB Output is correct
2 Correct 18 ms 18172 KB Output is correct
3 Correct 73 ms 79904 KB Output is correct
4 Correct 176 ms 174388 KB Output is correct
5 Correct 45 ms 51564 KB Output is correct
6 Correct 64 ms 76404 KB Output is correct
7 Correct 114 ms 143564 KB Output is correct
8 Correct 56 ms 54840 KB Output is correct
9 Correct 74 ms 91588 KB Output is correct
10 Correct 168 ms 196172 KB Output is correct
11 Correct 161 ms 195748 KB Output is correct
12 Correct 167 ms 196192 KB Output is correct
13 Correct 168 ms 196124 KB Output is correct
14 Correct 102 ms 196168 KB Output is correct
15 Correct 112 ms 196176 KB Output is correct
16 Incorrect 156 ms 182484 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 6 ms 10836 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 3 ms 3924 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 5 ms 7252 KB Output is correct
10 Correct 9 ms 12224 KB Output is correct
11 Incorrect 1 ms 496 KB Output isn't correct
12 Halted 0 ms 0 KB -