Submission #851460

#TimeUsernameProblemLanguageResultExecution timeMemory
851460askowGlobal Warming (CEOI18_glo)C++14
10 / 100
2081 ms5468 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N=2e5+50; signed main(){ int n,x; cin>>n>>x; int a[n+1]; for(int i=1;i<=n;i++)cin>>a[i]; if(x==0){ int lis=0; int Y[n+1]; for(int i=0;i<=n;i++)Y[i]=1e18; for(int i=1;i<=n;i++){ auto P=lower_bound(Y+1,Y+n+1,a[i])-Y; if(Y[P]==1e18)lis++; Y[P]=a[i]; } cout<<lis; return 0; } if(x==1e9){ int ans=0; int dp[n+1]; for(int i=0;i<=n;i++)dp[i]=1e18; int suf[n+1]; for(int i=0;i<=n;i++)suf[i]=1; int pref[n+1]; for(int i=0;i<=n;i++)pref[i]=0; for(int i=1;i<=n;i++){ auto P=lower_bound(dp+1,dp+n+1,a[i])-dp; if(dp[P]==1e18)pref[i]=pref[i-1]+1; else pref[i]=pref[i-1]; dp[P]=a[i]; } for(int i=n;i>=1;i--){ for(int j=i+1;j<=n;j++){ if(a[i]<a[j])suf[i]=max(suf[i],suf[j]+1); } } int S[n+2]; for(int i=0;i<=n+1;i++)S[i]=0; for(int i=n;i>=1;i--)S[i]=max(S[i+1],suf[i]); for(int i=1;i<n;i++){ ans=max(ans,pref[i]+S[i+1]); } cout<<ans; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...