Submission #820229

#	Time	Username	Problem	Language	Result	Execution time	Memory
820229		Zanite	Exam (eJOI20_exam)	C++17	65 / 100	461 ms	295500 KiB

exam

#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 / 14
• Subtask 2: 0 / 12
• Subtask 3: 13 / 13
• Subtask 4: 0 / 23
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22