Submission #833229

#TimeUsernameProblemLanguageResultExecution timeMemory
833229vjudge1Exam (eJOI20_exam)C++17
0 / 100
50 ms73292 KiB
#include<bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long int n; int a[100005], b[100005]; int memo[3000][3000]; int c[3000][3000]; int f(int last, int now){ // cout<<last<<' '<<now<<endl; if(now > n) return 0; int &ret = memo[last][now]; if(ret != -1) return ret; int mx = -1; for(int i=last; i<=now; i++){ mx = max(a[i], mx); } int cnt = 0; for(int i=last; i<=now; i++){ if(mx == b[i]) cnt++; } c[last][now] = cnt; ret = cnt; mx = 0; for(int i=now+1; i<=n; i++){ mx = max(mx, f(now+1, i)); } ret += mx; return ret; } int main(){ // ios::sync_with_stdio(0); cin.tie(0); cin>>n; bool sub2 = true; for(int i=1; i<=n; i++) cin>>a[i]; for(int i=1; i<=n; i++){ cin>>b[i]; if(i > 1 && b[i] != b[1]) sub2 = false; } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++) memo[i][j] = -1; } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++) c[i][j] = -1; } if(n <= 10){ int ans = -1; for(int i=1; i<=n; i++){ ans = max(ans, f(1, i)); } cout<<ans<<endl; } else if(sub2){ // cout<<"NYALA\n"; vector<int> id; int on[n+5]; memset(on, 0, sizeof(on)); for(int i=1; i<=n; i++){ if(a[i] == b[i]) id.push_back(i); } for(auto z: id){ if(!on[z]){ on[z] = 1; int x = z+1; while(x <= n && a[x] < a[z]){ on[x] = 1; x++; } x = z-1; while(x >= 1 && a[x] < a[z]){ on[x] = 1; x++; } } } int cnt = 0; for(int i=1; i<=n; i++){ if(on[i]) cnt++; } cout<<cnt<<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...