Submission #218890

#	Time	Username	Problem	Language	Result	Execution time	Memory
218890		socho	Visiting Singapore (NOI20_visitingsingapore)	C++14	23 / 100	545 ms	262148 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 = 5005;
const int MXK = 1005;

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

int best(int a, int b, int c, int d) {
	return dp[a][b][c][d];
}

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 day = n+1; day >= 1; day--) {
		for (int event = m+1; event >= 1; event--) {
			for (int last_day_taken=0; last_day_taken<2; last_day_taken++) {		
				for (int last_eve_taken=0; last_eve_taken<2; 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) {
						dp[day][event][last_day_taken][last_eve_taken] = 0; // done with trip, watched all events, bye (cant watch any more)
					}
					else 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
							dp[day][event][last_day_taken][last_eve_taken] = a + (m - event + 1) * b;
						}
						else {
							// i did skip last event so i must pay (skip) * B
							dp[day][event][last_day_taken][last_eve_taken] = (m - event + 1) * b;
						}
					}
					else {
						// 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
						}
						
						dp[day][event][last_day_taken][last_eve_taken] = opt;
					}
					
				}
			}
			int i = day;
			int j = event;
			int skipcost = (j - 1) * b + a;
			if (j - 1 == 0) skipcost = 0;
			int here = dp[i][j][1][1] + skipcost;
			MX = max(MX, here);
			// cout << "startday: " << i << " firstev: " << j << " " << here << endl;
		}
	}
	
	
	cout << MX << endl;
	
}

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