oj.uz

Submission #218890

# Submission time Handle Problem Language Result Execution time Memory
218890 2020-04-03T03:39:58 Z socho Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 545 ms 262148 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1408 KB Output is correct
2 Correct 34 ms 17528 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 7 ms 4224 KB Output is correct
5 Correct 5 ms 1920 KB Output is correct
6 Correct 14 ms 7168 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 8 ms 3328 KB Output is correct
9 Correct 20 ms 11008 KB Output is correct
10 Correct 37 ms 20088 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 13 ms 5248 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 7 ms 2048 KB Output is correct
6 Correct 20 ms 10240 KB Output is correct
7 Correct 21 ms 9856 KB Output is correct
8 Correct 28 ms 14464 KB Output is correct
9 Correct 8 ms 2432 KB Output is correct
10 Correct 37 ms 20092 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 49112 KB Output is correct
2 Correct 43 ms 25848 KB Output is correct
3 Correct 279 ms 144380 KB Output is correct
4 Runtime error 545 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 49112 KB Output is correct
2 Correct 43 ms 25848 KB Output is correct
3 Correct 279 ms 144380 KB Output is correct
4 Runtime error 545 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 49112 KB Output is correct
2 Correct 43 ms 25848 KB Output is correct
3 Correct 279 ms 144380 KB Output is correct
4 Runtime error 545 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 896 KB Output is correct
11 Correct 6 ms 1024 KB Output is correct
12 Correct 5 ms 888 KB Output is correct
13 Correct 5 ms 896 KB Output is correct
14 Correct 5 ms 896 KB Output is correct
15 Correct 5 ms 896 KB Output is correct

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1408 KB Output is correct
2 Correct 34 ms 17528 KB Output is correct
3 Correct 6 ms 1536 KB Output is correct
4 Correct 7 ms 4224 KB Output is correct
5 Correct 5 ms 1920 KB Output is correct
6 Correct 14 ms 7168 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 8 ms 3328 KB Output is correct
9 Correct 20 ms 11008 KB Output is correct
10 Correct 37 ms 20088 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 13 ms 5248 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 7 ms 2048 KB Output is correct
16 Correct 20 ms 10240 KB Output is correct
17 Correct 21 ms 9856 KB Output is correct
18 Correct 28 ms 14464 KB Output is correct
19 Correct 8 ms 2432 KB Output is correct
20 Correct 37 ms 20092 KB Output is correct
21 Correct 89 ms 49112 KB Output is correct
22 Correct 43 ms 25848 KB Output is correct
23 Correct 279 ms 144380 KB Output is correct
24 Runtime error 545 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -