oj.uz

Submission #113352

# Submission time Handle Problem Language Result Execution time Memory
113352 2019-05-25T06:53:11 Z 임유진(#2858) Boat (APIO16_boat) C++14
0 / 100
 507 ms 12172 KB 
#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-1][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];
		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-1; j++){
			if(((MOD-1)&(1<<j))!=0) inv[i]=inv[i]*p%MOD;
			p=p*p%MOD;
		}
	}
	for(int i=0; i<MAXN; i++) iCj[i][0]=1;
	for(int i=2; i<MAXN; i++) for(int j=1; j<=i; j++) iCj[i][j]=iCj[i-1][j-1]+iCj[i-1][j];
	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++){
		if(a[i]==c[0]) dp[i][0]=dp[i-1][0]+1;
		else dp[i][0]=dp[i-1][0]+2;
	}
	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=1; k<=i; k++) if(a[k]<=c[j-1]&&c[j]<=b[k]){
			//printf("*");
			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

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 507 ms 12172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 507 ms 12172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 4224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 507 ms 12172 KB Output isn't correct
2 Halted 0 ms 0 KB -