Submission #833369

#TimeUsernameProblemLanguageResultExecution timeMemory
833369vjudge1Exam (eJOI20_exam)C++17
0 / 100
56 ms74184 KiB
#include<bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long int n; int a[100005], b[100005]; int memo[100005]; int c[3000][3000]; int count(int l, int r){ if(c[l][r] != -1) return c[l][r]; int mx = -1; for(int i=l; i<=r; i++) mx = max(mx, a[i]); int cnt = 0; for(int i=l; i<=r; i++){ if(mx == b[i]) cnt++; } c[l][r] = cnt; return cnt; } int f(int now){ if(now <= 0) return 0; int &ret = memo[now]; if(ret != -1) return ret; ret = 0; for(int i=now; i>=1; i--){ ret = max(ret, f(i-1)+count(i, now)); } 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++){ memo[i] = -1; } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++) c[i][j] = -1; } if(n <= 10 && !sub2){ int ans = f(n); cout<<ans<<endl; // for(int i=1; i<=n; i++){ // cout<<memo[i]<<' '; // } } 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] == 0){ on[x] = 1; x++; } x = z-1; while(x >= 1 && a[x] <= a[z] && on[x] == 0){ 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...