제출 #224498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224498		Berted	Visiting Singapore (NOI20_visitingsingapore)	C++14	100 / 100	572 ms	884 KiB

VisitingSingapore

#include <bits/stdc++.h>
using namespace std;
const int MN = -1000069;
int k, n, m, a, b, dp[3][5001][4] = {}, v[1001], s[5001], t[5001];

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> k >> n >> m >> a >> b;
	for (int i = 0; i < k; i++) {cin >> v[i];}
	for (int i = 0; i < n; i++) {cin >> s[i];}
	for (int i = 0; i < m; i++) {cin >> t[i];}
	for (int i = 0; i <= m; i++)
	{
		for (int j = 0; j < 4; j++) {dp[0][i][j] = MN;}
	}
	dp[0][0][0] = 0;
	int ans = a + m * b;
	for (int i = 1; i <= n + m; i++)
	{
		for (int j = 0; j <= i && j <= m; j++)
		{
			for (int l = 0; l < 4; l++) {dp[i % 3][j][l] = MN;}
			int k = i - j;
			if (k > n) {continue;}
			if (j == 0) {dp[i % 3][j][0] = 0;}
			if (j && k && s[k- 1] == t[j - 1])
			{
				//cout << "ENTERED\n";
				for (int l = 0; l < 4; l++)
				{
					if (dp[(i - 2)%3][j - 1][l] != MN) dp[i % 3][j][0] = max(dp[i % 3][j][0], dp[(i - 2)%3][j - 1][l] + v[t[j - 1] - 1]);
				}
			}
			if (j)
			{
				if (dp[(i - 1)%3][j - 1][0] != MN) dp[i % 3][j][1] = max(dp[i % 3][j][1], dp[(i - 1)%3][j - 1][0] + a + b);
				if (dp[(i - 1)%3][j - 1][1] != MN) dp[i % 3][j][1] = max(dp[i % 3][j][1], dp[(i - 1)%3][j - 1][1] + b);
				if (dp[(i - 1)%3][j - 1][2] != MN) dp[i % 3][j][3] = max(dp[i % 3][j][3], dp[(i - 1)%3][j - 1][2] + a + b);
				if (dp[(i - 1)%3][j - 1][3] != MN) dp[i % 3][j][3] = max(dp[i % 3][j][3], dp[(i - 1)%3][j - 1][3] + b);
 			}
			if (k)
			{
				if (dp[(i - 1)%3][j][0] != MN) dp[i % 3][j][2] = max(dp[i % 3][j][2], dp[(i - 1)%3][j][0] + a + b);
				if (dp[(i - 1)%3][j][2] != MN) dp[i % 3][j][2] = max(dp[i % 3][j][2], dp[(i - 1)%3][j][2] + b);
				if (dp[(i - 1)%3][j][1] != MN) dp[i % 3][j][3] = max(dp[i % 3][j][3], dp[(i - 1)%3][j][1] + a + b);
				if (dp[(i - 1)%3][j][3] != MN) dp[i % 3][j][3] = max(dp[i % 3][j][3], dp[(i - 1)%3][j][3] + b);
			}
			if (j == m) 
			{
				ans = max({ans, dp[i % 3][j][0], dp[i % 3][j][1], dp[i % 3][j][2], dp[i % 3][j][3]});
			}
			//cout << j << " "<< k << " " << dp[i % 3][j][0] << " " << dp[i % 3][j][1] << " " << dp[i % 3][j][2] << " " << dp[i % 3][j][3] << "\n";
		}
	}
	cout << ans << "\n";
	return 0;
}

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