oj.uz

Submission #819298

# Submission time Handle Problem Language Result Execution time Memory
819298 2023-08-10T09:05:29 Z Zanite Exam (eJOI20_exam) C++17
0 / 100
 89 ms 117800 KB 
#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 = 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.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 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 117800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
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 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
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 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -