제출 #224165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224165		crimsonred	Visiting Singapore (NOI20_visitingsingapore)	C++17	100 / 100	724 ms	792 KiB

VisitingSingapore

#include <bits/stdc++.h>
using namespace std;

#define mod 1'000'000'007
typedef long long ll;

template<typename T>
void deb(initializer_list<T> l)
{
	for (auto &e : l)
		cout << e << ' ';
	cout << endl;
}

int k, n, m, a, b;
vector<int> v, s, t;
int dp[5001][5001][2][2];

void solve()
{
	cin >> k >> n >> m >> a >> b;
	v.resize(k);
	s.resize(n);
	t.resize(m);
	for (auto &e : v)
		cin >> e;
	for (auto &e : s)
		cin >> e;
	for (auto &e : t)
		cin >> e;

	int ans = -1e9;
	int i, j, k, l;
	for (i = n; i >= 0; --i)
	{
		for (j = m; j >= 0; --j)
		{
			for (k = 0; k < 2; ++k)
			{
				for (l = 0; l < 2; ++l)
				{
					if (j == m)
						dp[i % 2][j][k][l] = (k + l) * a;
					else if (i == n)
						dp[i % 2][j][k][l] = k * a + a + (m - j) * b;
					else
					{
						dp[i % 2][j][k][l] = max({k * a + a + (m - j) * b,
											b + dp[i % 2][j + 1][k][1],
											b + dp[(i + 1) % 2][j][1][l]});
						if (s[i] == t[j])
							dp[i % 2][j][k][l] = max(dp[i % 2][j][k][l],
										dp[(i + 1) % 2][j + 1][0][0] +
										(k + l) * a + v[t[j] - 1]);
					}

					if (!j && !k && !l)
						ans = max(ans, dp[i % 2][j][k][l]);
				}
			}
		}
	}
	
	// int ans = dp[0][0][0][0];
	// for (int i = 1; i < n; ++i)
	// 	ans = max(ans, dp[i][0][0][0]);
	cout << ans << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
	// cin >> t;
	while (t--)
		solve();

	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