Submission #463724

#	Time	Username	Problem	Language	Result	Execution time	Memory
463724		RaresFelix	Exam (eJOI20_exam)	C++17	0 / 100	22 ms	3532 KiB

exam

#include <bits/stdc++.h>
#define MN 107171
#define MM 5071

using namespace std;

int n, A[MN], B[MN];

void solve_equal() {
	int st = 1, re = 0, dr = n;
	for(int i = 1; i <= n; ++i){
		if(A[i] > B[i])
			st = i + 1;
		else if(A[i] == B[i]){
			re += i - st + 1;
			st = i + 1;
		}
	}
	for(int i = n; i >= 1; --i){
		if(A[i] > B[i])
			dr = i - 1;
		else if(A[i] == B[i]){
			re += dr - i + 1;
			--re;
			dr = i-1;
		}
	}
	cout << re << "\n";
}
int NR[MN];
vector<int> V[MN];
map<int, int> IA;
stack<int> Maxime;
int DP1[MN];
void solve_distinct(){
	for(int i = 1; i <= n; ++i) IA[A[i]] = i;
	for(int i = 1; i <= n; ++i) V[IA[B[i]]].push_back(i);
	for(int i = 1; i <= n; ++i) {
		while(!Maxime.empty() && A[i] > A[Maxime.top()])
			Maxime.pop();
		DP1[i] = DP1[i-1];
		//il legam pe A[i] la valoarile corespunzatoare de dinainte
		int nr = 0;
		for(auto it : V[i]){
			if(it > i) break;
			if(Maxime.empty() || it > Maxime.top()) // se poate adauga
				++nr;
		}
		for(auto it : V[i]){
			if(it > i) break;
			DP1[i] = max(DP1[i], DP1[it-1] + nr);
			if(Maxime.empty() || it > Maxime.top()) --nr;
		}
		if(IA[B[i]] < i && (Maxime.empty() || Maxime.top() <= IA[B[i]])) { // nu exista alt maxim
			++NR[IA[B[i]]];
			//il putem lega pe B[i] la A daca e optim
			DP1[i] = max(DP1[i], DP1[IA[B[i]]] + NR[IA[B[i]]]);
		}
		Maxime.push(i);
	}
	cout << DP1[n] << "\n";
}

int DP[MM][MM];
void solve(){
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j){
			DP[i][j] = max(DP[i-1][j], max(DP[i][j-1], DP[i-1][j-1]));
			if(A[i] == B[j])
				++DP[i][j];
		}
	cout << DP[n][n] << "\n";
}

int main() {
	cin >> n;
	int tip = 0;
	map<int, int> FA;
	for(int i = 1; i <= n; ++i)
		cin >> A[i];
	for(int i = 1; i <= n; ++i) {
		cin >> B[i];
		++FA[A[i]];
		if(i != 1 && B[i] != B[i-1]) tip |= 1;
		if(FA[A[i]] != 1) tip |= 2;
	}
	if(!(tip&1)) solve_equal();
	else if(!(tip&2)) solve_distinct();
	else solve();
    return 0;
}

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