Submission #691611

#	Time	Username	Problem	Language	Result	Execution time	Memory
691611		penguin133	Visiting Singapore (NOI20_visitingsingapore)	C++17	23 / 100	63 ms	528 KiB

VisitingSingapore

#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 = a + m * b;
	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);
		}
	}
	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 (stderr)

VisitingSingapore.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main(){
      | ^~~~

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 0 / 12
• Subtask 4: 0 / 7
• Subtask 5: 0 / 8
• Subtask 6: 13 / 13
• Subtask 7: 0 / 50