Submission #218889

#	Time	Username	Problem	Language	Result	Execution time	Memory
218889		socho	Visiting Singapore (NOI20_visitingsingapore)	C++14	13 / 100	7 ms	896 KiB

VisitingSingapore

#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
// #define double long double
// #define int long long
// int MOD = 1000 * 1000 * 1000 + 7;
// int MOD = 998244353;

const int MXN = 105;
const int MXK = 1005;

int k, n, m, a, b;
int hap[MXK];
int eve[MXN];
int want[MXN];
bool vis[MXN][MXN][2][2];
int dp[MXN][MXN][2][2];

int best(int day, int event, bool last_day_taken, bool last_eve_taken) {
	
	// my choices are:
	//  * skip today
	//  * skip wish
	//  * leave here
	// if todays event is wished, then also:
	//  * watch today's event
	
	if (event > m) {
		return 0; // done with trip, watched all events, bye (cant watch any more)
	}
	if (day > n) {
		// ran out of days
		// then i'm done anyway, how many events am i forced to skip?
		// if i skipped my last event, there's no surcharge here of A, just Bs
		if (last_eve_taken) {
			// so i didn't skip last event, so i must pay A + (skip) * B
			return a + (m - event + 1) * b;
		}
		else {
			// i did skip last event so i must pay (skip) * B
			return (m - event + 1) * b;
		}
	}
	
	if (vis[day][event][last_day_taken][last_eve_taken]) return dp[day][event][last_day_taken][last_eve_taken];
	vis[day][event][last_day_taken][last_eve_taken] = true;
	
	// i can just leave today and skip the rest
	int missing = m - event + 1;
	int opt = missing * b + a;
	if (last_eve_taken == false) {
		opt = missing * b;
	}
	
	// do i want to skip today?
	if (last_day_taken) {
		// last day was taken, so i need a and b to be paid
		opt = max(opt, a + b + best(day+1, event, 0, last_eve_taken)); // last day wont be taken anymore
	}
	else {
		// no need a surcharge
		opt = max(opt, b + best(day+1, event, 0, last_eve_taken));
	}
	
	// do i want to skip this wish?
	if (last_eve_taken) {
		// last event was taken so i need a and b to be paid
		opt = max(opt, a + b + best(day, event+1, last_day_taken, 0));
	}
	else {
		// no need a surcharge
		opt = max(opt, b + best(day, event+1, last_day_taken, 0));
	}
	
	// can i match this wish?
	if (eve[day] == want[event]) {
		// i can watch this!
		// cout << day << " " << event << endl;
		opt = max(opt, hap[want[event]] + best(day+1, event+1, 1, 1)); // all taken, next day, next event
	}
	
	return dp[day][event][last_day_taken][last_eve_taken] = opt;
	
	
}

signed main() {
	
	cin >> k >> n >> m >> a >> b;
	for (int i=1; i<=k; i++) cin >> hap[i];
	for (int i=1; i<=n; i++) cin >> eve[i];
	for (int i=1; i<=m; i++) cin >> want[i];
	
	int MX = INT_MIN;
	
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			int skipcost = (j - 1) * b + a;
			if (j - 1 == 0) skipcost = 0;
			int here = best(i, j, 1, 1) + skipcost;
			MX = max(MX, here);
			// cout << "startday: " << i << " firstev: " << j << " " << here << endl;
		}
	}
	
	cout << MX << 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