제출 #1310361

#제출 시각아이디문제언어결과실행 시간메모리
1310361samarthkulkarniVisiting Singapore (NOI20_visitingsingapore)C++20
4 / 100
2096 ms39684 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


const int KN = 1e3+10;
const int N = 5e3+10;
const long long inf = 1e18;

ll v[KN];
ll a[N];
ll b[N];

ll dp[N][N];

void solution() {

	ll s, n, m, A, B;
	cin >> s >> n >> m >> A >> B;
	for (int i = 0; i <= m; i++) {
		fill(dp[i], dp[i]+N, -inf);
	}

	for (int i = 1; i <= s; i++) cin >> v[i];
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) cin >> b[i];



	ll ans = 0;


	for (int i = m; i >= 1; i--) {
		for (int j = n; j >= 1; j--) {
			for (int k = j+1; k <= n; k++) {


				if (b[i] == a[j]) {

					dp[i][j] = max(dp[i][j], 
						v[b[i]] + dp[i+1][k] + (k != j+1 ? A + (k-j-1)*B : 0));

				} else {

					dp[i][j] = max(dp[i][j], B + dp[i+1][k] + (b[i+1] == a[k] ? A : 0));
				}

			}

			ans = max(ans, dp[i][j]);
		}

	}


	cout << ans << endl;
}
#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...