Submission #832877

#	Time	Username	Problem	Language	Result	Execution time	Memory
832877		NK_	Visiting Singapore (NOI20_visitingsingapore)	C++17	23 / 100	204 ms	262144 KiB

VisitingSingapore

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);

int main() {
	cin.tie(0)->sync_with_stdio(0);
  	
	int K, N, M, A, B; cin >> K >> N >> M >> A >> B;

	vi H(K); for(auto& x : H) cin >> x;
	vi S(N); for(auto& x : S) { cin >> x; --x; }
	vi T(M); for(auto& x : T) { cin >> x; --x; }

	int dp[N+1][2][M+1][2];
	memset(dp, 0xc0, sizeof(dp));

	// can start on any day
	for(int i = 0; i <= N; i++) dp[i][1][0][1] = 0;	

	int ans = -MOD;
	for(int x = 0; x <= N; x++) for(int y = 0; y <= M; y++) {
		for(int ys = 0; ys <= 1; ys++) for(int xs = 0; xs <= 1; xs++) {


			if (y == M) {
				// cerr << x << " " << xs << " " << y << " " << ys << endl;
				// cerr << dp[x][xs][y][ys] << endl;
				ans = max(dp[x][xs][y][ys], ans);
			}

			// go to event
			if (x < N && y < M && S[x] == T[y]) dp[x+1][1][y+1][1] = max(dp[x][xs][y][ys] + H[T[y]], dp[x+1][1][y+1][1]);

			// skip next event in S (x)
			if (x < N) dp[x+1][0][y][ys] = max(dp[x][xs][y][ys] + B + xs * A, dp[x+1][0][y][ys]);

			// skip next event in T (y)
			if (y < M) dp[x][xs][y+1][0] = max(dp[x][xs][y][ys] + B + ys * A, dp[x][xs][y+1][0]);
		}
	}

	cout << ans << nl;

    return 0;	
} 	

• 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