oj.uz

Submission #691629

# Submission time Handle Problem Language Result Execution time Memory
691629 2023-01-31T10:58:04 Z penguin133 Visiting Singapore (NOI20_visitingsingapore) C++17
4 / 100
 29 ms 536 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[2][5005][2][2];
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])dp[x][j][0][0] = dp[1-x][j-1][0][0] + V[S[i]];
			else dp[x][j][0][0] = max(dp[1-x][j][0][0], dp[x][j-1][0][0]);
			res = max(res, dp[x][j][0][0]);
		}
	}
	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:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main(){
      | ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct

Subtask #2
0 / 6.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 436 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Incorrect 29 ms 536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 436 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Incorrect 29 ms 536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 436 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Incorrect 29 ms 536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -