Submission #259073

#	Time	Username	Problem	Language	Result	Execution time	Memory
259073		ryangohca	Visiting Singapore (NOI20_visitingsingapore)	C++17	100 / 100	850 ms	888 KiB

VisitingSingapore

#include <bits/stdc++.h>
#define int long long
using namespace std;
int places[5001];
vector<int> happy;
vector<int> favourites;
int n, m, a, b;
int memo[2][5001][2][2];
main(){
	int k; cin >> k >> n >> m >> a >> b;
	happy.push_back(0);
	for (int i = 0; i < k; i++){
		int g; cin >> g;
		happy.push_back(g);
	}
	for (int i = 0; i < n; i++){
		cin >> places[i];
	}
	for (int i = 0; i < m; i++){
		int g; cin >> g;
		favourites.push_back(g);
	}
	int ans = a + m * b;
	int idx = 0;
	for (int i = 10000; i >= 0; i--){
		for (int j = m - 1; j >= 0; j--){
			for (int st = false; st <= true; st++){
				for (int sf = false; sf <= true; sf++){
					int ans = a + (m - j) * b;
					if (!st) ans = max(ans, memo[1 - idx][j][true][false] + a + b);
					else ans = max(ans, memo[1 - idx][j][true][false] + b);
					if (!sf) ans = max(ans, memo[idx][j + 1][false][true] + a + b);
					else ans = max(ans, memo[idx][j + 1][false][true] + b);
					if (i < n && places[i] == favourites[j]) ans = max(ans, memo[1-idx][j+1][false][false] + happy[places[i]]);
					memo[idx][j][st][sf] = ans;
				}
			}
		}
		if (i < n)ans = max(ans, memo[idx][0][false][false]);
		idx = 1 - idx;
	}
	cout << ans << endl;
}

Compilation message (stderr)

VisitingSingapore.cpp:9:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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