Submission #211247

#	Time	Username	Problem	Language	Result	Execution time	Memory
211247		socho	Visiting Singapore (NOI20_visitingsingapore)	C++14	42 / 100	2090 ms	99324 KiB

VisitingSingapore

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

const int MXK = 1005;
const int MXN = 5005;
const int MXM = 5005;
int k, n, m, a, b;
int happy[MXK];
int events[MXN];
int want[MXM];

int dp[MXN][MXM];

int solve(int planday, int realday) {
	if (planday == m) return 0; // if we're at end of plan, no more to gain
	if (realday == n) {
		// no more days to do anything
		int re = (m - planday);
		int co = (re == 0) ? 0 : b * re + a;
		return co;
	}
	if (dp[planday][realday] != INT_MIN) return dp[planday][realday];
	int best = INT_MIN; // the best is nada
	// let's say we skip this day of plan
	// there are then m - planday - 1 remaining in plan so 
	for (int u=planday; u<m; u++) {
		// skip until day u of plan
		int skip = (u - planday + 1);
		int cost = ((skip == 0) ? 0 : b * skip + a);
		best = max(best, cost + solve(u+1, realday));
	}
	// to match this plan day to some other day
	for (int i=realday; i<n; i++) {
		if (events[i] == want[planday]) {
			// we can do this planday on i day
			// we'll be skipping i - realday days
			int cost = ((i - realday == 0) ? 0 : b * (i - realday) + a);
			int gain = happy[events[i]];
			// then we'll end up on the day after i
			best = max(best, gain + cost + solve(planday+1, i+1));
		}
	}
	
	return dp[planday][realday] = best;
}

int lcs(int i, int j) {
	if (i == n && j == m) {
		return 0;
	}
	if (i == n) {
		return lcs(i, j+1) + b;
	}
	if (j == m) {
		return lcs(i+1, j);
	}
	if (dp[i][j] != INT_MIN) return dp[i][j];
	int best = INT_MIN;
	if (events[i] == want[j]) {
		best = max(best, happy[events[i]] + lcs(i+1, j+1));
	}
	int g = m-j;
	best = max(best, (g==0)?0:g*b);
	best = max(best, lcs(i+1, j) + b);
	best = max(best, lcs(i, j+1) + b);
	return dp[i][j] = best;
}

int main() {
	
	for (int i=0; i<MXN; i++) for (int j=0; j<MXM; j++) dp[i][j] = INT_MIN;
	
	cin >> k >> n >> m >> a >> b;
	for (int i=1; i<=k; i++) cin >> happy[i];
	for (int i=0; i<n; i++) cin >> events[i];
	for (int i=0; i<m; i++) cin >> want[i];
	
	if (k == 1) {
		
		if (n >= m) {
			cout << m * happy[1] << endl;
		}
		else {
			cout << n * happy[1] + ((m-n) * b + a) << endl;
		}
		
		exit(0);
	}
	
	if (a == 0) {
		
		int opt = INT_MIN;
		for (int i=0; i<n; i++) opt = max(opt, lcs(i, 0));
		cout << opt << endl;
		exit(0);
		
	}
	
	int mx = INT_MIN;
	for (int i=0; i<n; i++) mx = max(mx, solve(0, i));
	cout << mx << endl;
	
}

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