This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |