Submission #819315

#	Time	Username	Problem	Language	Result	Execution time	Memory
819315		Zanite	Exam (eJOI20_exam)	C++17	0 / 100	140 ms	197088 KiB

exam

#include <bits/stdc++.h>
using namespace std;

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

void chmax(int &x, int y) {x = max(x, y);}

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

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;
	}
	
	// Base case
	dp[0][0][0] = -iINF;
	dp[0][0][1] = 0;
	for (int c = 1; c <= N; c++) {
		for (int d = 0; d <= 1; d++) {
			dp[0][c][d] = -iINF;
		}
	}
	mx[0][0] = -iINF;
	mx[0][1] = 0;
	for (int i = 1; i <= N; i++) {
		for (int c = 1; c < A[i]; c++) dp[i][c][0] = dp[i][c][1] = -iINF;
		for (int c = A[i]; c <= M; c++) {
			int inc = (c == B[i]);
			dp[i][c][0] = dp[i][c][1] = -iINF;

			// dp[i][c][0]

			// Create new segment
			chmax(dp[i][c][0], mx[i-1][1]);
			// Continue previous segment
			chmax(dp[i][c][0], dp[i-1][c][0]);

			// dp[i][c][1]

			if (c == A[i]) {
				// Complete previous segment
				chmax(dp[i][c][1], dp[i-1][c][0]);
				// Create new complete segment
				chmax(dp[i][c][1], mx[i-1][1]);
			}
			// Continue previous complete segment
			chmax(dp[i][c][1], dp[i-1][c][1]);
			
			dp[i][c][0] += inc;
			dp[i][c][1] += inc;

			// cout << "dp[" << i << "][" << c << "] = " << dp[i][c][0] << ' ' << dp[i][c][1] << '\n';
		}

		for (int d = 0; d <= 1; d++) {
			mx[i][d] = -iINF;
			for (int c = A[i]; c <= M; c++) {
				chmax(mx[i][d], dp[i][c][d]);
			}
		}
	}

	int ans = -iINF;
	for (int i = A[N]; i <= M; i++) chmax(ans, dp[N][i][1]);
	cout << ans << '\n';
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22