제출 #1310547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310547		samarthkulkarni	Visiting Singapore (NOI20_visitingsingapore)	C++20	100 / 100	138 ms	1092 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);}

static int dp[N][2][2][2];
static int ndp[N][2][2][2];
static int wa[N][2][2][2];

void solution() {

	for (int i = 0; i < N; i++) {
		for (int l = 0; l < 2; l++) {
			for (int r = 0; r < 2; r++) {
				wa[i][l][r][0] = wa[i][l][r][1] = -1e9;
			}
		}
	}

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

	int addL[2] = {0, A};
	int addR[2] = {0, A};

	memcpy(dp, wa, sizeof(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--) {		

		memcpy(ndp, wa, sizeof(ndp));

		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] + addL[l]);
						mx(ndp[j][l][r][st], 2*B + dp[j+1][0][0][1] + addR[r] + addL[l]);
						mx(ndp[j][l][r][st], B + ndp[j+1][l][0][1] + addR[r]);

					}


				}
			}
		}

		memcpy(dp, ndp, sizeof(dp));
	}

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





}

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