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){
// cout << i << " " << sblm << endl;
ada = false;
ans += i-sblm-1;
}
sblm = i;
}
}
cout << ans << endl;
exit(0);
}
if(cnt2 == n){
for(ll i = 1; i <= n; i++){
par[i] = -1;
for(ll j = i; j <= n; j++){
if(a[j] > b[i]) break;
if(a[j] == b[i]){
par[i] = j;
break;
}
}
}
for(ll i = n; i >= 1; i--){
if(par[i] == -1){
dp[i] = dp[i+1];
continue;
}
ll tmp = 1;
for(ll j = i+1; j <= par[i]; j++){
if(par[j] == -1) continue;
dp[i] = max(dp[i], tmp+dp[j]);
if(par[j] >= par[i]) tmp++;
}
// cout << tmp << " " <<par[i] << " " << dp[par[i]] << endl;
}
// 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... |