oj.uz

Submission #820229

# Submission time Handle Problem Language Result Execution time Memory
820229 2023-08-11T01:49:43 Z Zanite Exam (eJOI20_exam) C++17
65 / 100
 461 ms 295500 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;

namespace Subtask2 {
	void solve() {
		int qb = B[1];
		int ans = 0, run = 0;
		bool hasB = false;
		for (int i = 1; i <= N; i++) {
			if (A[i] > qb) {
				run = 0;
				hasB = false;
				continue;
			}

			run++;
			if (A[i] == qb) {hasB = true;}
			if (hasB) {
				ans += run;
				run = 0;
			}
		}
		cout << ans << '\n';
	}
}

namespace Subtask4 {
	void solve() {
		exit(-1);
	}
}

namespace Subtask6 {
	int dp[maxN][maxN], mx[maxN][maxN], pf[maxN][maxN];

	void solve() {
		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';
	}
}

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;
	}

	bool allEqualB = true;
	for (int i = 2; i <= N; i++) {
		if (B[i] != B[1]) allEqualB = false;
	}

	const int sub6Limit = 5000;

	if (allEqualB) {
		Subtask2::solve();
	} else if (sub6Limit) {
		Subtask6::solve();
	} else {
		Subtask4::solve();
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 5 ms 860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 5 ms 9300 KB Output is correct
3 Correct 53 ms 71508 KB Output is correct
4 Correct 369 ms 283660 KB Output is correct
5 Correct 399 ms 295320 KB Output is correct
6 Correct 396 ms 295500 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 295384 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 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 1 ms 3156 KB Output is correct
13 Correct 1 ms 3156 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 5 ms 9300 KB Output is correct
9 Correct 53 ms 71508 KB Output is correct
10 Correct 369 ms 283660 KB Output is correct
11 Correct 399 ms 295320 KB Output is correct
12 Correct 396 ms 295500 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 1 ms 3156 KB Output is correct
19 Correct 1 ms 3156 KB Output is correct
20 Correct 2 ms 3156 KB Output is correct
21 Correct 2 ms 3156 KB Output is correct
22 Correct 14 ms 24148 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 384 ms 295308 KB Output is correct
25 Correct 410 ms 295344 KB Output is correct
26 Correct 404 ms 295312 KB Output is correct
27 Correct 461 ms 295260 KB Output is correct
28 Correct 391 ms 295336 KB Output is correct
29 Correct 394 ms 295364 KB Output is correct
30 Correct 410 ms 295256 KB Output is correct
31 Correct 406 ms 295244 KB Output is correct
32 Correct 410 ms 295316 KB Output is correct