oj.uz

답안 #820220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
820220 2023-08-11T01:38:06 Z Zanite Exam (eJOI20_exam) C++17
65 / 100
 557 ms 295416 KB 
#include <bits/stdc++.h>
using namespace std;

const int iINF	= 1e9;
const int maxN	= 5023;

int N, M, A[maxN], B[maxN];
vector<int> compress;
int dp[maxN][maxN], mx[maxN][maxN], pf[maxN][maxN];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		compress.push_back(A[i]);
	}
	for (int i = 1; i <= N; i++) {
		cin >> B[i];
		compress.push_back(B[i]);
	}

	sort(compress.begin(), compress.end());
	compress.erase(unique(compress.begin(), compress.end()), compress.end());
	M = compress.size();
	for (int i = 1; i <= N; i++) {
		A[i] = lower_bound(compress.begin(), compress.end(), A[i]) - compress.begin() + 1;
		B[i] = lower_bound(compress.begin(), compress.end(), B[i]) - compress.begin() + 1;
	}
	
	for (int l = 1; l <= N; l++) {
		mx[l][l] = A[l];
		for (int r = l+1; r <= N; r++) {
			mx[l][r] = max(mx[l][r-1], A[r]);
			mx[r][l] = mx[l][r];
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int val = 1; val <= N; val++) {
			pf[i][val] = -iINF;
		}
	}

	pf[0][0] = 0;
	for (int i = 1; i <= N; i++) {
		for (int val = 1; val <= N; val++) {
			if (mx[val][i] == A[val]) {
				dp[i][val] = pf[i-1][val] + (B[i] == A[val]);
				// cout << "dp[" << i << "][" << val << "] = " << dp[i][val] << '\n';
			} else {
				dp[i][val] = -iINF;
			}

			pf[i][val] = max(pf[i][val-1], dp[i][val]);
		}
	}

	int ans = pf[N][N];
	cout << ans << '\n';
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 24180 KB Output is correct
2 Runtime error 7 ms 852 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 4 ms 9300 KB Output is correct
3 Correct 57 ms 71500 KB Output is correct
4 Correct 408 ms 283568 KB Output is correct
5 Correct 552 ms 295288 KB Output is correct
6 Correct 540 ms 295404 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 552 ms 295396 KB Output is correct
2 Runtime error 6 ms 852 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 2 ms 3156 KB Output is correct
12 Correct 2 ms 3156 KB Output is correct
13 Correct 2 ms 3184 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct

Subtask #6
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 4 ms 9300 KB Output is correct
9 Correct 57 ms 71500 KB Output is correct
10 Correct 408 ms 283568 KB Output is correct
11 Correct 552 ms 295288 KB Output is correct
12 Correct 540 ms 295404 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 1 ms 1620 KB Output is correct
16 Correct 2 ms 3156 KB Output is correct
17 Correct 2 ms 3156 KB Output is correct
18 Correct 2 ms 3156 KB Output is correct
19 Correct 2 ms 3184 KB Output is correct
20 Correct 2 ms 3156 KB Output is correct
21 Correct 2 ms 3156 KB Output is correct
22 Correct 17 ms 24152 KB Output is correct
23 Correct 532 ms 295384 KB Output is correct
24 Correct 535 ms 295352 KB Output is correct
25 Correct 557 ms 295416 KB Output is correct
26 Correct 535 ms 295400 KB Output is correct
27 Correct 533 ms 295372 KB Output is correct
28 Correct 533 ms 295400 KB Output is correct
29 Correct 527 ms 295316 KB Output is correct
30 Correct 549 ms 295396 KB Output is correct
31 Correct 530 ms 295372 KB Output is correct
32 Correct 554 ms 295356 KB Output is correct