Submission #1253733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253733		onur8ocak	Exam (eJOI20_exam)	C++20	65 / 100	1095 ms	6212 KiB

exam

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N=2e5+5;
void solve(){
	int n; cin >> n;
	int a[N+5],b[N+5];
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i=1;i<=n;i++){
		cin >> b[i];
	}
	stack<int> s;
	int l[n+5],r[n+5];
	for(int i=1;i<=n;i++){
		while(s.size()&&a[s.top()]<=a[i]){
			s.pop();
		}
		if(s.size()){
			l[i]=s.top();
		}
		else{
			l[i]=0;
		}
		s.push(i);
	}
	stack<int> ss;
	for(int i=n;i>=1;i--){
		while(ss.size()&&a[ss.top()]<=a[i]){
			ss.pop();
		}
		if(ss.size()){
			r[i]=ss.top();
		}
		else{
			r[i]=n+1;
		}
		ss.push(i);
	}
	//for(int i=1;i<=4;i++){
	//	cout << l[i] << r[i] << endl;
	//}
	vector<int> dp(n+5,0);
	int ans=0;
	for(int i=1;i<=n;i++){
		int mx=0;
		for(int j=1;j<=n;j++){
			mx=max(mx,dp[j]);
			if(l[j]<i&&i<r[j]&&a[j]==b[i]){
				dp[j]=mx+1;
			}
			ans=max(ans,dp[j]);
		}
	}
	//for(int i=1;i<=n;i++){
	//	ans=max(ans,dp[i]);
	//}
	cout << ans << endl;
}

int32_t main(){
	solve();
	return 0;
}

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