Submission #1310361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310361		samarthkulkarni	Visiting Singapore (NOI20_visitingsingapore)	C++20	4 / 100	2096 ms	39684 KiB

VisitingSingapore

#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;
}

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