제출 #224166

#제출 시각아이디문제언어결과실행 시간메모리
224166crimsonredVisiting Singapore (NOI20_visitingsingapore)C++17
100 / 100
703 ms632 KiB
#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[2][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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...