Submission #60137221

---

Source Code Expand

#include<bits/stdc++.h>
#include"atcoder/all"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> P;
const ll mod=998244353;
const ll inf=1ll<<61;
typedef modint998244353 mi;

int op(int x,int y){return max(x,y);}
int e(){return 0;}

vector<int>LIS(vector<int>&V){
	int N=V.size();
	vector<int>ans(N);
	vector<pair<int,int>>VP;
	rep(i,N)VP.push_back({V[i],-i});
	sort(VP.begin(),VP.end());
	rep(i,N)VP[i].second*=-1;
	segtree<int,op,e>S(N);
	rep(i,N){
		S.set(VP[i].second,S.prod(0,VP[i].second)+1);
	}
	rep(i,N)ans[i]=S.get(i);
	return ans;
}

int main(){
	int n;cin>>n;
	vector<int>a(n);
	rep(i,n)cin>>a[i];
	vector<int>rev=a;
	reverse(all(rev));

	vector<int>lis_a=LIS(a),lis_r=LIS(rev);
	int ans=0;
	rep(i,n)ans=max(ans,lis_a[i]+lis_r[n-1-i]-1);
	cout<<ans<<endl;
}

Submission Info

Judge Result