제출 #1310540

#제출 시각아이디문제언어결과실행 시간메모리
1310540samarthkulkarniVisiting Singapore (NOI20_visitingsingapore)C++20
23 / 100
2094 ms3076 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 = -1e9+7;
// int dp[N][N][2][2][2];

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

#define vr vector<vector<vector<vector<int>>>>  
void vii(vr &w) {
	vr temp(n+5, vector<vector<vector<int>>>(2, vector<vector<int>>(2, vector<int>(2, -1e9))));
	w = move(temp);
}


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

	// for (int i = 0; i <= m+5; i++) {
	// 	for (int j = 0; j <= n+5; j++) {
	// 		for (int t = 0; t < 2; t++) {
	// 			for (int l = 0; l < 2; l++) {
	// 				dp[i][j][t][l][0] = dp[i][j][t][l][1] = 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];


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


	// for (int i = 1; i <= m; i++) {
	// 	for (int j = 0; j < 2; j++) {
	// 		for (int l = 0; l < 2; l++) {
	// 			dp[i][n+1][j][l][1] = cost(i, m);
	// 			dp[i][n+1][j][l][0] = -1e9;
	// 		}
	// 	}
	// }
	// for (int i = 1; i <= n+1; i++) {
	// 	for (int j = 0; j < 2; j++) {
	// 		for (int l = 0; l < 2; l++) {
	// 			dp[m+1][i][j][l][1] = 0;
	// 			dp[m+1][i][j][l][0] = -1e9;
	// 		}
	// 	}
	// }
	// dp[m+1][n+1][1][1][0] = -1e9;	


	vr dp;
	vii(dp);
	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+5, 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);
	}



	// for (int i = m; i >= 1; i--) {
	// 	for (int j = n; j >= 1; j--) {
	// 		dp[i][j][1][1][0] = dp[i][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(dp[i][j][l][r][st], v[b[i]]+dp[i+1][j+1][1][1][1]); 
	// 					}
	// 					mx(dp[i][j][l][r][st], B + dp[i+1][j][0][r][1] + (l?A:0));
	// 					mx(dp[i][j][l][r][st], 2*B + dp[i+1][j+1][0][0][1] + (l?A:0) + (r?A:0));
	// 					mx(dp[i][j][l][r][st], B + dp[i][j+1][l][0][1] + (r?A:0));
	// 				}
	// 			}
	// 		}
	// 	}
	// }

	cout << dp[1][1][1][0] << 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...