This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
typedef long long ll;
const ll MAXN = 1e5 + 5;
const ll INF = 1e9;
#define endl '\n'
#define pll pair <ll, ll>
#define fi first
#define se second
ll n;
ll a [MAXN], b [MAXN];
ll par [MAXN];
ll dp [MAXN];
ll bpk(ll x){
if(par[x] == x) return x;
return par[x] = bpk(par[x]);
}
int main(){
cin >> n;
ll cnt2 = 0;
for(ll i = 1; i <= n; i++){
cin >> a[i];
if(a[i-1] < a[i]) cnt2++;
}
ll cnt = 0;
for(ll i = 1; i <= n; i++){
cin >> b[i];
if(b[1] == b[i]) cnt++;
}
if(cnt == n){
ll sblm = 0;
bool ada = false;
ll ans = 0;
a[n+1] = 2*INF;
for(ll i = 1; i <= n+1; i++){
if(a[i] == b[1]) ada = true;
if(a[i] > b[1]){
if(ada){
ada = false;
ans += i-sblm-1;
sblm = i;
}
}
}
cout << ans << endl;
exit(0);
}
if(cnt2 == n){
for(ll i = 1; i <= n; i++){
for(ll j = i; j <= n; j++){
if(a[j] > b[i]){
par[i] = -1;
}
if(a[j] == b[i]){
par[i] = j;
break;
}
}
}
for(ll i = n; i >= 1; i--){
dp[i] = dp[i+1];
if(par[i] == -1) continue;
ll tmp = 1;
for(ll j = i+1; j <= par[i]-1; j++){
if(par[j] == -1) continue;
if(par[j] == par[i]) tmp++;
if(par[j] > par[i]){
dp[i] = max(dp[i], tmp+dp[j]);
}
}
// cout << tmp << " " <<par[i] << " " << dp[par[i]] << endl;
dp[i] = max(dp[i], tmp+dp[par[i]]);
}
// for(ll i = 1; i <= n; i++){
// cout << dp[i] << " ";
// }
// cout << endl;
cout << dp[1] << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |