Submission #918147

#TimeUsernameProblemLanguageResultExecution timeMemory
918147KiaRezExam (eJOI20_exam)C++17
65 / 100
150 ms199796 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define endl '\n' const int N = 3e5+23, lg = 18; ll Mod = 1e9+7; //998244353; inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;} inline ll poww(ll a, ll b, ll mod=Mod) { ll ans = 1; a=MOD(a, mod); while (b) { if (b & 1) ans = MOD(ans*a, mod); b >>= 1; a = MOD(a*a, mod); } return ans; } int t, n, pos[N], a[N], b[N], pd[5005], mx[5005][5005], dp[5005][5005]; vector<int> comp; int main () { ios_base::sync_with_stdio(false), cin.tie(0); cin>>n; if (n > 5000) kill(0); for(int i=1; i<=n; i++) cin>>a[i], comp.pb(a[i]); for(int i=1; i<=n; i++) cin>>b[i]; sort(all(comp)); comp.resize(unique(all(comp)) - comp.begin()); for(int i=1; i<=n; i++) { int ptr = lower_bound(all(comp), a[i]) - comp.begin() + 1; a[i] = ptr; mx[i][i] = a[i]; ptr = lower_bound(all(comp), b[i]) - comp.begin(); if(ptr>=0 && ptr<size(comp) && comp[ptr]==b[i]) b[i] = ptr+1; else b[i] = 0; } for(int l=1; l<=n; l++) for(int r=l+1; r<=n; r++) mx[l][r] = max(mx[l][r-1], mx[r][r]); for(int i=1; i<=n; i++) dp[1][i] = (b[i]==a[i] && mx[1][i]==a[i]); for(int i=1; i<=n; i++) { int maxi = 0; for(int j=1; j<=n; j++) { maxi = max(maxi, dp[i-1][j]); if(mx[min(i,j)][max(i,j)] == a[j]) { dp[i][j] = maxi + (b[i] == a[j]); } } } int ans = 0; for(int i=1; i<=n; i++) ans = max(ans, dp[n][i]); cout<<ans<<endl; 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...