oj.uz

Submission #463724

# Submission time Handle Problem Language Result Execution time Memory
463724 2021-08-11T15:41:07 Z RaresFelix Exam (eJOI20_exam) C++17
0 / 100
 22 ms 3532 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Incorrect 2 ms 2892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Incorrect 22 ms 3348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2816 KB Output is correct
2 Incorrect 3 ms 2824 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Incorrect 2 ms 2892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Incorrect 2 ms 2892 KB Output isn't correct
3 Halted 0 ms 0 KB -