Submission #163029

#	Time	Username	Problem	Language	Result	Execution time	Memory
163029		HungAnhGoldIBO2020	Boat (APIO16_boat)	C++14	0 / 100	668 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());
	i=0;
	j=0;
	rev[0]=1;
	for(i=1;i<=n;i++){
		rev[i]=binpow(i,mod-2);
	}
	while(i<ope.size()){
		while(j<ope.size()&&ope[j].first==ope[i].first){
			used[ope[j].second]^=1;
			j++;
		}
		for(k=1;k<=n;k++){
			sum[k]=sum[k-1]+used[k];
		}
		if(j==ope.size()){
			break;
		}
		int len=ope[j].first-ope[i].first,val=sum[n],c1=1,c2=1;
		for(k=1;k<=min(len,val);k++){
			c1=1;
			c2=1;
			choose[k]=0;
			for(l=0;l<k;l++){
				choose[k]+=c1*c2;
				choose[k]%=mod;
				c1=c1*(len-l);
				c1%=mod;
				c1=c1*rev[l+1];
				c1%=mod;
				c2=c2*(val-l);
				c2%=mod;
				c2=c2*rev[l+1];
				c2%=mod;
			}
		}
		ndp[0]=1;
		for(k=1;k<=n;k++){
			for(l=0;l<k;l++){
				ndp[k]+=dp[l]*choose[sum[k]-sum[l]];
				ndp[k]%=mod;
			}
		}
		for(k=0;k<=n;k++){
			dp[k]=ndp[k];
		}
		i=j;
	}
	int ans=0;
	for(i=1;i<=n;i++){
		ans+=dp[i];
		if(ans>=mod){
			ans-=mod;
		}
	}
	cout<<ans;
}

Compilation message (stderr)

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

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