Submission #389087

#	Time	Username	Problem	Language	Result	Execution time	Memory
389087		mosiashvililuka	Boat (APIO16_boat)	C++14	36 / 100	2003 ms	20772 KiB

boat

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,fma")
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,mod=1000000007LL,sub1,f[3009],DPI[3009],pas,li,dp[3009],dpp[3009],dp2[3009][509],dpp2[3009][509],fct[509],C[3009][509],len[3009],wu[3009];
pair <long long, long long> p[3009],l[5009];
map <long long, long long> m,n;
map <long long, long long>::iterator it,tt;
long long xar(long long q, long long w){
	if(w==0) return 1LL;
	long long qw=xar(q,w/2);
	if(w%2==0) return (qw*qw)%mod; else return ((qw*qw)%mod*q)%mod;
}
long long dv(long long q, long long w){
	return (q*xar(w,mod-2))%mod;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(i=1; i<=a; i++){
		cin>>p[i].first>>p[i].second;
		if(p[i].first!=p[i].second){
			sub1=1;
		}
	}
	if(sub1==0){
		DPI[a]=1;
		for(i=a-1; i>=1; i--){
			for(j=i+1; j<=a; j++){
				if(p[j].first>p[i].first){
					DPI[i]+=DPI[j];
					if(DPI[i]>=mod) DPI[i]-=mod;
				}
			}
			DPI[i]++;
			if(DPI[i]>=mod) DPI[i]-=mod;
		}
		for(i=1; i<=a; i++){
			pas+=DPI[i];
			if(pas>=mod) pas-=mod;
		}
		cout<<pas;
		return 0;
	}
	for(i=1; i<=a; i++){
		m[p[i].first]=1;
		m[p[i].second]=1;
	}
	
	for(it=m.begin(); it!=m.end(); it++){
		li++;
		l[li].first=(*it).first;
		l[li].second=(*it).first;
		tt=it;tt++;
		if(tt!=m.end()&&(*it).first+1<=(*tt).first-1){
			li++;
			l[li].first=(*it).first+1;
			l[li].second=(*tt).first-1;
		}
	}
	/*cout<<li<<endl;
	for(i=1; i<=li; i++){
		cout<<l[i].first<<" "<<l[i].second<<endl;
	}*/
	for(i=1; i<=li; i++){
		n[l[i].first]=l[i].second;
	}
	for(i=1; i<=li; i++){
		len[i]=l[i].second-l[i].first+1;
		C[i][0]=1;
		for(j=1; j<=min(a,len[i]); j++){
			zx=dv(len[i]-j+1,j);
			C[i][j]=(C[i][j-1]*zx)%mod;
			//cout<<len[i]<<" "<<j<<"  "<<C[i][j]<<endl;
		}
	}
	for(ii=a; ii>=1; ii--){
		for(i=0; i<=li+2; i++){
			dpp[i]=dp[i];
			for(j=0; j<=a+2; j++){
				dpp2[i][j]=dp2[i][j];
			}
		}
		for(i=1; i<=li; i++){
			if(l[i].second<p[ii].first||l[i].first>p[ii].second) continue;
			wu[i]++;
			for(j=i+1; j<=li; j++){
				/*dpp[i]+=dp[j]*len[i];
				dpp[i]%=mod;*/
				dpp2[i][1]+=dp[j];
				if(dpp2[i][1]>=mod) dpp2[i][1]-=mod;
			}
			dpp2[i][1]++;
			if(dpp2[i][1]>=mod) dpp2[i][1]-=mod;
			for(j=1; j<wu[i]; j++){
				dpp2[i][j+1]+=dp2[i][j];
				if(dpp2[i][j+1]>=mod) dpp2[i][j+1]-=mod;
			}
			dpp[i]=0;
			for(j=1; j<=wu[i]; j++){
				//if(j>len[i]) break;
				dpp[i]+=dpp2[i][j]*C[i][j];
				//if(dpp[i]>=mod) dpp[i]-=mod;
				dpp[i]%=mod;
			}
		}
		for(i=1; i<=li; i++){
			dp[i]=dpp[i];
			for(j=0; j<=a+2; j++){
				dp2[i][j]=dpp2[i][j];
			}
		}
/*		for(i=1; i<=li; i++) cout<<dp[i]<<" ";
		cout<<endl;*/
	}
	//cout<<dp2[2][1]<<endl;
	
	pas=0;
	for(i=1; i<=li; i++){
		pas+=dp[i];
		if(pas>=mod) pas-=mod;
	}
	cout<<pas;
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42