Submission #42609

#	Time	Username	Problem	Language	Result	Execution time	Memory
42609		fefe	Boat (APIO16_boat)	C++14	0 / 100	2 ms	376 KiB

boat

#include<bits/stdc++.h>
#define MAX_N 505
#define MOD 1000000007LL
#define pb push_back
typedef long long LL;
using namespace std;
struct node{
	LL s,e;
}arr[MAX_N];
LL n,ans,inv[MAX_N];
LL t[MAX_N][5*MAX_N],sum[MAX_N][5*MAX_N];
vector<LL> X;
LL Pow(LL x,LL y){
	if(y==0)	return 1;
	if(y==1)	return x;
	LL z=pow(x,y/2);
	z*=z;z%=MOD;
	if(y%2)	z*=x;
	z%=MOD;
	return z;
}
int main(){
	LL i,j,k,s,e,x,y,S,E,cnt;
	scanf("%lld",&n);
	for(i=1;i<=n;i++){
		scanf("%lld %lld",&arr[i].s,&arr[i].e);
		X.pb(arr[i].s);X.pb(arr[i].e);
	}
	for(i=1;i<=1000;i++)	inv[i]=Pow(i,MOD-2);
	sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());
	t[0][0]=sum[0][0]=1;
	for(i=1;i<=4*n+1;i++)	sum[0][i]=1;
	for(i=1;i<=n;i++){
		S=lower_bound(X.begin(),X.end(),arr[i].s)-X.begin();
		E=lower_bound(X.begin(),X.end(),arr[i].e)-X.begin();
		for(j=2*S+1;j<=2*E+1;j++){
			s=j%2?X[j/2]:X[j/2-1]+1;
			e=j%2?X[j/2]:X[j/2]-1;
			if(s>e)	continue;
			cnt=1;
			x=1;
			t[i][j]=(sum[i-1][j-1]*(e-s+1))%MOD;
			if(e==s)	continue;
			for(k=i-1;k>=1;k--){
				if(arr[k].s>s || arr[k].e<e)	continue;
				cnt++;
				x*=(e-s-1+cnt);x%=MOD;x*=inv[cnt];x%=MOD;
				t[i][j]=(t[i][j]+sum[k-1][j-1]*x)%MOD;				
			}
		}
		sum[i][0]=sum[i-1][0];
		for(j=1;j<=4*n+1;j++){
			sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+t[i][j]+MOD)%MOD;
		}
	}
	printf("%lld\n",sum[n][4*n+1]-1);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:23:17: warning: unused variable 'y' [-Wunused-variable]
  LL i,j,k,s,e,x,y,S,E,cnt;
                 ^
boat.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
boat.cpp:26:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&arr[i].s,&arr[i].e);
                                         ^
boat.cpp:29:42: warning: iteration 504u invokes undefined behavior [-Waggressive-loop-optimizations]
  for(i=1;i<=1000;i++) inv[i]=Pow(i,MOD-2);
                                          ^
boat.cpp:29:11: note: containing loop
  for(i=1;i<=1000;i++) inv[i]=Pow(i,MOD-2);
           ^

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