oj.uz

Submission #218889

# Submission time Handle Problem Language Result Execution time Memory
218889 2020-04-03T03:28:09 Z socho Visiting Singapore (NOI20_visitingsingapore) C++14
13 / 100
 7 ms 896 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 = 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.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

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

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -