Submission #113373

#	Time	Username	Problem	Language	Result	Execution time	Memory
113373		kajebiii	Boat (APIO16_boat)	C++17	100 / 100	1389 ms	14344 KiB

boat

#include<stdio.h>
#include<algorithm>
 
using namespace std;
 
#define MAXN 500
#define MOD 1000000007
 
long long inv[MAXN+1];
long long iCj[MAXN][MAXN], diCj[2*MAXN][MAXN+1];
long long g[MAXN][2*MAXN];
long long dp[MAXN+1][2*MAXN];
 
int main(){
	int N;
	int a[MAXN+1], b[MAXN+1];
	int c[2*MAXN], cn=1;
	int d[2*MAXN];
 
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d%d", a+i, b+i);
 
	for(int i=1; i<=N; i++){
		c[i*2-2]=a[i]-1;
		c[i*2-1]=b[i];
	}
	sort(c, c+2*N);
	for(int i=1; i<2*N; i++) if(c[i]!=c[i-1]) c[cn++]=c[i];
	for(int i=1; i<cn; i++) d[i]=c[i]-c[i-1];
 
	for(int i=1; i<=MAXN; i++){
		inv[i]=1;
		long long p=i;
		for(int j=0; (1<<j)<=MOD-2; j++){
			if(((MOD-2)&(1<<j))!=0) inv[i]=inv[i]*p%MOD;
			p=p*p%MOD;
		}
	}
	for(int i=0; i<N; i++) iCj[i][0]=1;
	for(int i=1; i<N; i++) for(int j=1; j<=i; j++) iCj[i][j]=(iCj[i-1][j-1]+iCj[i-1][j])%MOD;
	for(int i=1; i<cn; i++){
		diCj[i][0]=1;
		for(int j=1; j<=d[i]&&j<=N; j++){
			diCj[i][j]=diCj[i][j-1]*(d[i]-j+1)%MOD*inv[j]%MOD;
			//printf("%lld ", diCj[i][j]);
		}
		//printf("\n");
	}
	for(int i=0; i<N; i++) for(int j=1; j<cn; j++){
		g[i][j]=0;
		for(int k=0; k<=i; k++)
			g[i][j]=(g[i][j]+iCj[i][k]*diCj[j][k+1]%MOD)%MOD;
	}
 
	/*
	for(int i=0; i<N; i++){
		for(int j=1; j<cn; j++) printf("%lld ", g[i][j]);
		printf("\n");
	}
	*/
 
	for(int i=0; i<cn; i++) dp[0][i]=1;
	for(int i=1; i<=N; i++) dp[i][0]=1;
	for(int i=1; i<=N; i++) for(int j=1; j<cn; j++){
		dp[i][j]=dp[i][j-1];
		int f=0;
		for(int k=i; k>0; k--) if(a[k]<=c[j-1]+1&&c[j]<=b[k]){
			//printf("%lld{%d} ", dp[i][j], f);
			dp[i][j]=(dp[i][j]+g[f++][j]*dp[k-1][j-1]%MOD)%MOD;
		}
		//printf("(%d %d %lld)\n", i, j, dp[i][j]);
	}
 
	printf("%lld", (dp[N][cn-1]-1+MOD)%MOD);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
boat.cpp:21:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d%d", a+i, b+i);
                          ~~~~~^~~~~~~~~~~~~~~~~~

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