Submission #1310542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310542		samarthkulkarni	Visiting Singapore (NOI20_visitingsingapore)	C++20	23 / 100	2096 ms	3076 KiB

VisitingSingapore

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

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("fast-math") 


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


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 = -1e9+7;

int v[KN];
int a[N];
int b[N];
int s, n, m, A, B;



int cost(int i, int j) {
	if (i > j) return 0;
	return A + (j-i+1)*B;
}

void mx(int &x, int y) {x = max(x, y);}



void solution() {
	cin >> s >> n >> m >> A >> B;


	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];


	bool f1 = false;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i] == b[j]) {f1 = true; break;}
		}
	}

	if (!f1) {
		cout << cost(1, m) << endl;
		return;
	}


	vr dp(n+2, vector<vector<vector<int>>>(2, vector<vector<int>>(2, vector<int>(2, -1e9))));

	for (int i = 1; i <= n+1; i++) {
		for (int l = 0; l < 2; l++) {
			for (int r = 0; r < 2; r++) {
				dp[i][l][r][1] = 0;
			}
		}
	}


	for (int i = m; i >= 1; i--) {
		vr ndp(n+2, vector<vector<vector<int>>>(2, vector<vector<int>>(2, vector<int>(2, -1e9))));

		for (int l = 0; l < 2; l++) {
			for (int r = 0; r < 2; r++) {
				ndp[n+1][l][r][1] = cost(i, m);
			}
		}

		for (int j = n; j >= 1; j--) {

			ndp[j][1][1][0] = ndp[j+1][1][1][0];

			for (int l = 0; l < 2; l++) {
				for (int r = 0; r < 2; r++) {
					for (int st = 0; st < 2; st++) {

						if (b[i] == a[j]) {
							mx(ndp[j][l][r][st], v[b[i]]+dp[j+1][1][1][1]);
						}

						mx(ndp[j][l][r][st], B + dp[j][0][r][1] + (l?A:0));
						mx(ndp[j][l][r][st], 2*B + dp[j+1][0][0][1] + (l?A:0) + (r?A:0));
						mx(ndp[j][l][r][st], B + ndp[j+1][l][0][1] + (r?A:0));

					}


				}
			}
		}
		dp = move(ndp);
	}

	cout << dp[1][1][1][0] << endl;





}

• 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