Submission #1310507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310507		samarthkulkarni	Visiting Singapore (NOI20_visitingsingapore)	C++20	13 / 100	2 ms	1344 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 = 110;
const long long inf = -1e9+7;
ll dp[N][N][2][2][2];

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



ll cost(int i, int j) {
	if (i > j) return 0;
	return A + (j-i+1)*B;
}
ll solve(int i, int j, bool t1, bool t2, bool st) {
	// if ((i > m || j > n) && !st) return -1e9;
	// if (j > n) return cost(i, m);
	// if (i > m) return 0;

	if (dp[i][j][t1][t2][st] != inf) return dp[i][j][t1][t2][st];
	ll ans = -1e9;
	if (!st) ans = solve(i, j+1, t1, t2, false);
	if (b[i] == a[j]) {
		ans = max(ans, v[b[i]] + solve(i+1, j+1, true, true, true));
	}
	ans = max({ans, 
		B + solve(i+1, j, false, t2, st) + (t1?A : 0),
		2*B + solve(i+1, j+1, false, false, st) + (t1?A:0) + (t2?A:0),
		B + solve(i, j+1, t1, false, st) + (t2?A:0)
	});
	return dp[i][j][t1][t2][st] = ans;
}






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




	cout << solve(1, 1, 1, 1, 0) << endl;
}

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