Submission #231713

#	Time	Username	Problem	Language	Result	Execution time	Memory
231713		kshitij_sodani	Boat (APIO16_boat)	C++17	0 / 100	1218 ms	16376 KiB

boat

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define a first
#define b second
#define pb push_back
llo n,aa,bb;
map<llo,llo> dd;
llo si[2001];
llo mod=1000000007;
vector<llo> cc;
vector<pair<llo,llo>> it;
llo fac[501];
llo fac2[501];
llo pre[2001][501];
llo pre2[2001][501];
llo com[501][501];
llo dp[501][2001];
llo ind2=0;

llo mod2(llo ee,llo ff){
	if(ff==0){
		return 1;
	}
	llo ans=mod2(ee,ff/2);
	ans*=ans;
	ans%=mod;
	if(ff%2==1){
		ans*=ee;
		ans%=mod;
	}
	return ans;
}
void comp(){
	fac[0]=1;
	for(llo i=1;i<501;i++){
		fac[i]=fac[i-1]*i;
		fac[i]%=mod;
	}
	for(llo i=0;i<501;i++){
		fac2[i]=mod2(fac[i],mod-2);
	}
}
void ncr(){
	for(llo i=0;i<n+1;i++){
		for(llo j=0;j<=i;j++){
			com[i][j]=fac2[j]*fac2[i-j];
			com[i][j]%=mod;
			com[i][j]*=fac[i];
			com[i][j]%=mod;
			//cout<<i<<"      "<<j<<" "<<com[i][j]<<endl;
		//	cout<<fac[i]<<"   "<<fac2[j]<<"   "<<fac2[i-j]<<endl;
		}
	}
}
void comp2(){
	fac[0]=1;
	for(llo i=0;i<ind2;i++){
		llo cur=1;
		pre[i][0]=0;
		for(llo j=1;j<n+1;j++){
			if(j<=si[i]){
				cur*=mod2(j,mod-2);
				cur%=mod;
				cur*=(si[j]-j+1);
				cur%=mod;
				pre[i][j]=cur;
				pre[i][j]+=pre[i][j-1];
				pre[i][j]%=mod;
			}
			else{
				pre[i][j]=pre[i][j-1];
			}
		}		
	}
	for(llo i=0;i<ind2;i++){
		for(llo j=1;j<n+1;j++){
			pre2[i][j]=0;
			for(llo k=1;k<=j;k++){
				pre2[i][j]+=pre[i][k]*com[j-1][k-1];
				pre2[i][j]%=mod;
			}
			//cout<<i<<"::"<<j<<" "<<pre2[i][j]<<endl;
		}
	}
}

int main(){
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>aa>>bb;
		cc.pb(aa);
		cc.pb(bb);
		it.pb({aa,bb});
	}
	comp();//factorial
	ncr();//computing iCj for i and j from 1 to n
	sort(cc.begin(),cc.end());
	for(llo i=0;i<cc.size();i++){
		if(i<cc.size()-1 and cc[i]==cc[i+1]){
			continue;
		}
		dd[cc[i]]=ind2;
		ind2+=1;

		si[dd[cc[i]]]=1;
		if(i<cc.size()-1){
			if(cc[i]<cc[i+1]-1){
				si[ind2]=cc[i+1]-cc[i]-1;
				ind2+=1;
			}
		}
	}
	comp2();
	for(llo i=0;i<n;i++){
		it[i].a=dd[it[i].a];
		it[i].b=dd[it[i].b];
	}


	for(llo i=0;i<n;i++){
		for(llo j=0;j<ind2;j++){
			dp[i][j]=0;
		}
	}
	for(llo j=0;j<ind2;j++){
		if(j>=it[0].a and j<=it[0].b){
			dp[0][j]=si[j];
		}
		if(j>0){
			dp[0][j]+=dp[0][j-1];
		}
		dp[0][j]%=mod;
	}
	for(llo i=1;i<n;i++){
		for(llo j=it[i].a;j<=it[i].b;j++){
			llo cot=1;
			for(llo k=i-1;k>=0;k--){
				if(j>0){
					dp[i][j]+=(dp[k][j-1]+1)*pre2[j][cot];
					dp[i][j]%=mod;
				}
				else{
					dp[i][j]+=pre2[j][cot];
					dp[i][j]%=mod;
				}
				if(it[k].a<=j and j<=it[k].b){
					cot+=1;
				}
			}
		}
		for(llo j=1;j<ind2;j++){
			dp[i][j]+=dp[i][j-1];
			dp[i][j]%=mod;
		}
	}
	llo ans=0;
	for(llo i=0;i<n;i++){
	//	for(llo j=it[i].a;j<=it[i].b;j++){
			ans+=dp[i][ind2-1];
			ans%=mod;
		//cout<<i<<",,"<<j<<",,"<<dp[i][j]<<endl;

	//	}
	}
//	cout<<dp[0][0]<<","<<dp[0][1]<<","<<dp[1][1]<<","<<dp[1][2]<<endl;
	cout<<ans<<endl;







	
	
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:101:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo i=0;i<cc.size();i++){
              ~^~~~~~~~~~
boat.cpp:102:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<cc.size()-1 and cc[i]==cc[i+1]){
      ~^~~~~~~~~~~~
boat.cpp:109:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<cc.size()-1){
      ~^~~~~~~~~~~~

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