Submission #163032

#	Time	Username	Problem	Language	Result	Execution time	Memory
163032		HungAnhGoldIBO2020	Boat (APIO16_boat)	C++14	100 / 100	986 ms	508 KiB

boat

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=502;
const int mod=1e9+7;
int used[N],sum[N],dp[N],ndp[N],choose[N],rev[N];
vector<pair<int,int> > ope;
int binpow(int x,int y){
	int tich=1;
	while(y){
		if(y&1){
			tich*=x;
			tich%=mod;
		}
		x*=x;
		x%=mod;
		y>>=1;
	}
	return tich;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>j>>k;
		k++;
		ope.push_back({j,i});
		ope.push_back({k,i});
	}
	sort(ope.begin(),ope.end());
	rev[0]=1;
	for(i=1;i<=n;i++){
		rev[i]=binpow(i,mod-2);
	}
	i=0;
	j=0;
	dp[0]=1;
	while(i<ope.size()){
		while(j<ope.size()&&ope[j].first==ope[i].first){
			used[ope[j].second]^=1;
			j++;
		}
		if(j==ope.size()){
			break;
		}
		for(k=1;k<=n;k++){
			sum[k]=sum[k-1]+used[k];
			choose[k]=0;
			//cout<<sum[k]<<' ';
		}
		//cout<<endl;
		int len=ope[j].first-ope[i].first,val=sum[n],c1,c2;
		//cout<<len<<' '<<val<<endl;
		for(k=1;k<=val;k++){
			c1=len;
			c2=1;
			assert(k<=n);
			for(l=0;l<min(k,len+1);l++){
				choose[k]+=c1*c2;
				choose[k]%=mod;
				c1=c1*(len-l-1);
				c1%=mod;
				c1=c1*rev[l+2];
				c1%=mod;
				c2=c2*(k-l-1);
				c2%=mod;
				c2=c2*rev[l+1];
				c2%=mod;
			}
		}
		for(k=0;k<=n;k++){
			ndp[k]=dp[k];
			if(used[k]){
				for(l=0;l<k;l++){
					ndp[k]+=dp[l]*choose[sum[k]-sum[l]];
//					if(k==2){
//						cout<<l<<' '<<dp[l]<<' '<<choose[sum[k]-sum[l]]<<' '<<sum[k]-sum[l]<<endl;
//					}
					ndp[k]%=mod;
				}
			}
		}
		for(k=0;k<=n;k++){
			dp[k]=ndp[k];
		//	cout<<dp[k]<<' ';
		}
		//cout<<"cac"<<endl;
		i=j;
	}
	int ans=0;
	for(i=1;i<=n;i++){
		ans+=dp[i];
		if(ans>=mod){
			ans-=mod;
		}
	}
	cout<<ans;
}
/*
3
1 2
3 4
5 6
3
1 2
4 5
7 8
26
*/

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:40:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<ope.size()){
        ~^~~~~~~~~~~
boat.cpp:41:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<ope.size()&&ope[j].first==ope[i].first){
         ~^~~~~~~~~~~
boat.cpp:45:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j==ope.size()){
      ~^~~~~~~~~~~~

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