Submission #224152

#	Time	Username	Problem	Language	Result	Execution time	Memory
224152		crimsonred	Visiting Singapore (NOI20_visitingsingapore)	C++17	23 / 100	445 ms	262148 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 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][j][k][l] = (k + l) * a;
					else if (i == n)
						dp[i][j][k][l] = k * a + a + (m - j) * b;
					else
					{
						dp[i][j][k][l] = max({k * a + a + (m - j) * b,
											  b + dp[i][j + 1][k][1],
											  b + dp[i + 1][j][1][l]});
						if (s[i] == t[j])
							dp[i][j][k][l] = max(dp[i][j][k][l],
										dp[i + 1][j + 1][0][0] +
										(k + l) * a + v[t[j] - 1]);
					}
				}
			}
		}
	}

	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: 0 / 12
• Subtask 4: 0 / 7
• Subtask 5: 0 / 8
• Subtask 6: 13 / 13
• Subtask 7: 0 / 50