oj.uz

Submission #832897

# Submission time Handle Problem Language Result Execution time Memory
832897 2023-08-21T16:27:13 Z NK_ Visiting Singapore (NOI20_visitingsingapore) C++17
12 / 100
 525 ms 496 KB 
// 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[2][M+1][2], ndp[2][M+1][2];
	memset(dp, 0xc0, sizeof(dp));

	int ans = -MOD;
	for(int x = 0; x <= N; x++) {
		// memset(ndp, 0xc0, sizeof(ndp));

		// can start on any day
		dp[1][0][1] = 0;

		for(int y = 0; y <= M; y++) for(int ys = 0; ys <= 1; ys++) for(int xs = 0; xs <= 1; xs++) {
			if (y == M) ans = max(dp[xs][y][ys], ans);

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

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

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

		for(int y = 0; y <= M; y++) for(int ys = 0; ys <= 1; ys++) for(int xs = 0; xs <= 1; xs++) {
			swap(dp[ys][y][xs], ndp[ys][y][xs]); ndp[ys][y][xs] = -MOD;
		}
	}

	cout << ans << nl;

    return 0;	
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 18 ms 352 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Incorrect 1 ms 320 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 340 KB Output is correct
2 Correct 17 ms 340 KB Output is correct
3 Correct 147 ms 388 KB Output is correct
4 Correct 351 ms 472 KB Output is correct
5 Correct 102 ms 340 KB Output is correct
6 Correct 148 ms 340 KB Output is correct
7 Correct 274 ms 436 KB Output is correct
8 Correct 90 ms 340 KB Output is correct
9 Correct 178 ms 432 KB Output is correct
10 Correct 441 ms 496 KB Output is correct
11 Correct 435 ms 468 KB Output is correct
12 Correct 443 ms 468 KB Output is correct
13 Correct 437 ms 496 KB Output is correct
14 Correct 518 ms 492 KB Output is correct
15 Correct 525 ms 488 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 340 KB Output is correct
2 Correct 17 ms 340 KB Output is correct
3 Correct 147 ms 388 KB Output is correct
4 Correct 351 ms 472 KB Output is correct
5 Correct 102 ms 340 KB Output is correct
6 Correct 148 ms 340 KB Output is correct
7 Correct 274 ms 436 KB Output is correct
8 Correct 90 ms 340 KB Output is correct
9 Correct 178 ms 432 KB Output is correct
10 Correct 441 ms 496 KB Output is correct
11 Correct 435 ms 468 KB Output is correct
12 Correct 443 ms 468 KB Output is correct
13 Correct 437 ms 496 KB Output is correct
14 Correct 518 ms 492 KB Output is correct
15 Correct 525 ms 488 KB Output is correct
16 Incorrect 228 ms 432 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 340 KB Output is correct
2 Correct 17 ms 340 KB Output is correct
3 Correct 147 ms 388 KB Output is correct
4 Correct 351 ms 472 KB Output is correct
5 Correct 102 ms 340 KB Output is correct
6 Correct 148 ms 340 KB Output is correct
7 Correct 274 ms 436 KB Output is correct
8 Correct 90 ms 340 KB Output is correct
9 Correct 178 ms 432 KB Output is correct
10 Correct 441 ms 496 KB Output is correct
11 Correct 435 ms 468 KB Output is correct
12 Correct 443 ms 468 KB Output is correct
13 Correct 437 ms 496 KB Output is correct
14 Correct 518 ms 492 KB Output is correct
15 Correct 525 ms 488 KB Output is correct
16 Incorrect 375 ms 468 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 18 ms 352 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Incorrect 1 ms 320 KB Output isn't correct
5 Halted 0 ms 0 KB -