Submission #875911

#TimeUsernameProblemLanguageResultExecution timeMemory
875911maxFedorchukExam (eJOI20_exam)C++14
65 / 100
177 ms99292 KiB
#include<bits/stdc++.h> #define FOR(i, begin, end) for(int i=(begin); i<(end); i++) using namespace std; const int N=5e3+10, L=28; int n, a[N], b[N], st[N][L], dp[N][N]; void build() { FOR(i, 1, L) { for(int j=1; j+(1<<i)-1<=n; j++) { st[j][i]=max(st[j][i-1], st[j+(1<<(i-1))][i-1]); } } } int get(int l, int r) { int ln=r-l+1; int k=0; while((1<<(k+1))<=ln) { k++; } return max(st[l][k], st[r-(1<<k)+1][k]); } int main() { cin >> n; FOR(i, 0, n) { cin >> a[i+1]; st[i+1][0]=a[i+1]; } FOR(i, 0, n) cin >> b[i+1]; build(); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(a[i]==b[j]) { int mx=get(min(i, j), max(i, j)); if(mx==a[i]) { dp[i][j]+=max(dp[i][j-1], dp[i-1][j-1])+1; } else { dp[i][j]=max({ dp[i-1][j], dp[i][j-1], dp[i-1][j-1] }); } } else { dp[i][j]=max({ dp[i-1][j], dp[i][j-1] , dp[i-1][j-1] }); } } } cout << dp[n][n]<<"\n"; 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...