제출 #1069311

#제출 시각아이디문제언어결과실행 시간메모리
1069311ten_xdExam (eJOI20_exam)C++17
0 / 100
2 ms860 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
#define fi first
#define se second

const int N = 5005, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;

int n;
int A[N], B[N];
int dp[N];

void solve()
{
	cin >> n;
	rep(i,n) cin >> A[i];
	rep(i,n) cin >> B[i];

	rep(i,n)
	{
		if(i == 0) dp[i] = 0;
		else dp[i] = dp[i-1];

		int czy = 0, il = 0;
		for(int j = i; j >= 0 and A[j] <= B[i]; --j)
		{
			if(A[j] == B[i]) czy = 1;
			if(B[j] == B[i]) ++il;
			int cost = il;
			if(j-1 >= 0) cost += dp[j-1];
			if(czy) dp[i] = max(dp[i],cost);
		}
		//cout << "I: " << i << " DP: " << dp[i] << '\n';
	}
	cout << dp[n-1] << '\n';
}

int main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
   	//cin >> T;
    while(T--) solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...