oj.uz

답안 #832893

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
832893 2023-08-21T16:25:44 Z NK_ Visiting Singapore (NOI20_visitingsingapore) C++17
12 / 100
 516 ms 500 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++) {
		// 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 19 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 340 KB Output is correct
2 Correct 17 ms 336 KB Output is correct
3 Correct 143 ms 340 KB Output is correct
4 Correct 361 ms 472 KB Output is correct
5 Correct 128 ms 444 KB Output is correct
6 Correct 153 ms 444 KB Output is correct
7 Correct 274 ms 340 KB Output is correct
8 Correct 111 ms 368 KB Output is correct
9 Correct 190 ms 340 KB Output is correct
10 Correct 439 ms 500 KB Output is correct
11 Correct 450 ms 488 KB Output is correct
12 Correct 474 ms 492 KB Output is correct
13 Correct 455 ms 500 KB Output is correct
14 Correct 514 ms 492 KB Output is correct
15 Correct 516 ms 488 KB Output is correct

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 340 KB Output is correct
2 Correct 17 ms 336 KB Output is correct
3 Correct 143 ms 340 KB Output is correct
4 Correct 361 ms 472 KB Output is correct
5 Correct 128 ms 444 KB Output is correct
6 Correct 153 ms 444 KB Output is correct
7 Correct 274 ms 340 KB Output is correct
8 Correct 111 ms 368 KB Output is correct
9 Correct 190 ms 340 KB Output is correct
10 Correct 439 ms 500 KB Output is correct
11 Correct 450 ms 488 KB Output is correct
12 Correct 474 ms 492 KB Output is correct
13 Correct 455 ms 500 KB Output is correct
14 Correct 514 ms 492 KB Output is correct
15 Correct 516 ms 488 KB Output is correct
16 Incorrect 242 ms 428 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 340 KB Output is correct
2 Correct 17 ms 336 KB Output is correct
3 Correct 143 ms 340 KB Output is correct
4 Correct 361 ms 472 KB Output is correct
5 Correct 128 ms 444 KB Output is correct
6 Correct 153 ms 444 KB Output is correct
7 Correct 274 ms 340 KB Output is correct
8 Correct 111 ms 368 KB Output is correct
9 Correct 190 ms 340 KB Output is correct
10 Correct 439 ms 500 KB Output is correct
11 Correct 450 ms 488 KB Output is correct
12 Correct 474 ms 492 KB Output is correct
13 Correct 455 ms 500 KB Output is correct
14 Correct 514 ms 492 KB Output is correct
15 Correct 516 ms 488 KB Output is correct
16 Incorrect 380 ms 468 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 19 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -