Submission #314523

#	Time	Username	Problem	Language	Result	Execution time	Memory
314523		kshitij_sodani	Zoltan (COCI16_zoltan)	C++14	70 / 140	1093 ms	5752 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n' 
llo mod=1e9+7;
llo n;
llo it[200001];
pair<llo,llo> dp[200001];
pair<llo,llo> dp2[200001];
llo pre[200001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	for(llo i=0;i<n/2;i++){
		swap(it[i],it[n-i-1]);
	}


	pre[0]=1;
	for(llo i=1;i<=n;i++){
		pre[i]=(pre[i-1]*2)%mod;
	}
	dp[0]={1,1};
	for(llo i=0;i<n;i++){
		llo ma=0;
		for(llo j=0;j<i;j++){
			if(it[j]<it[i]){
				ma=max(ma,dp[j].a);
			}
		}
		if(ma==0){
			dp[i]={1,1};
		}
		else{
			dp[i]={ma+1,0};
			for(llo j=0;j<i;j++){
				if(it[j]<it[i]){
					if(dp[j].a==ma){
						dp[i].b=(dp[i].b+dp[j].b)%mod;
					}
				}
			}
		}
	}
	

	dp2[0]={1,1};
	for(llo i=0;i<n;i++){
		llo ma=0;
		for(llo j=0;j<i;j++){
			if(it[j]>it[i]){
				ma=max(ma,dp2[j].a);
			}
		}
		if(ma==0){
			dp2[i]={1,1};
		}
		else{
			dp2[i]={ma+1,0};
			for(llo j=0;j<i;j++){
				if(it[j]>it[i]){
					if(dp2[j].a==ma){
						dp2[i].b=(dp2[i].b+dp2[j].b)%mod;
					}
				}
			}
		}
	}
	for(llo i=0;i<n/2;i++){
		swap(dp[i],dp[n-i-1]);
	}
	for(llo i=0;i<n/2;i++){
		swap(dp2[i],dp2[n-i-1]);
	}
/*	for(llo i=0;i<n;i++){
		cout<<dp[i].a<<":"<<dp[i].b<<endl;
	}
	cout<<endl;
	for(llo i=0;i<n;i++){
		cout<<dp2[i].a<<":"<<dp2[i].b<<endl;
	}
	cout<<endl;*/
	llo ans=0;
	llo ma=0;
	for(llo i=0;i<n;i++){
		ma=max(ma,dp[i].a+dp2[i].a-1);
	}
	for(llo i=0;i<n;i++){
		if(dp[i].a+dp2[i].a-1==ma){
			llo ans2=(dp[i].b*dp2[i].b)%mod;
			ans2=(ans2*pre[n-ma])%mod;
			/*if(i>0){
				ans2=(ans2*2)%mod;
			}*/
			ans=(ans2+ans)%mod;
			//cout<<ans2<<":";
		}
	}
	cout<<ma<<" "<<ans<<endl;

/*	vector<vector<pair<llo,llo>>> ss;
	ss.pb({{-it[i],1}});
	vector<vector<pair<llo,llo>>> tt;
	tt.pb({{it[i],1}});
	for(llo i=1;i<n;i++){
		if(it[i]==it[0]){
			continue;
		}
		llo xx=it[i];
		else if(it[i]<it[0]){


		}
		else{
			if(xx<=tt[0].back().a){

			}
			if(xx>tt[tt.size()-1].back().a){
				tt
			}

		}

	}*/






	return 0;
}

• Subtask 1: 70 / 140