oj.uz

Submission #113354

# Submission time Handle Problem Language Result Execution time Memory
113354 2019-05-25T07:23:49 Z 임유진(#2858) Boat (APIO16_boat) C++14
9 / 100
 1000 ms 14308 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]-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];
	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

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

# Verdict Execution time Memory Grader output
1 Correct 963 ms 14072 KB Output is correct
2 Correct 938 ms 14044 KB Output is correct
3 Correct 940 ms 14100 KB Output is correct
4 Correct 967 ms 14156 KB Output is correct
5 Correct 975 ms 14188 KB Output is correct
6 Correct 763 ms 14076 KB Output is correct
7 Correct 760 ms 14196 KB Output is correct
8 Correct 761 ms 14076 KB Output is correct
9 Correct 764 ms 14172 KB Output is correct
10 Correct 728 ms 14148 KB Output is correct
11 Correct 745 ms 14216 KB Output is correct
12 Correct 738 ms 14080 KB Output is correct
13 Correct 744 ms 14308 KB Output is correct
14 Correct 724 ms 14072 KB Output is correct
15 Correct 744 ms 14200 KB Output is correct
16 Correct 167 ms 8292 KB Output is correct
17 Correct 177 ms 8428 KB Output is correct
18 Correct 172 ms 8348 KB Output is correct
19 Correct 179 ms 8508 KB Output is correct
20 Correct 173 ms 8436 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 14072 KB Output is correct
2 Correct 938 ms 14044 KB Output is correct
3 Correct 940 ms 14100 KB Output is correct
4 Correct 967 ms 14156 KB Output is correct
5 Correct 975 ms 14188 KB Output is correct
6 Correct 763 ms 14076 KB Output is correct
7 Correct 760 ms 14196 KB Output is correct
8 Correct 761 ms 14076 KB Output is correct
9 Correct 764 ms 14172 KB Output is correct
10 Correct 728 ms 14148 KB Output is correct
11 Correct 745 ms 14216 KB Output is correct
12 Correct 738 ms 14080 KB Output is correct
13 Correct 744 ms 14308 KB Output is correct
14 Correct 724 ms 14072 KB Output is correct
15 Correct 744 ms 14200 KB Output is correct
16 Correct 167 ms 8292 KB Output is correct
17 Correct 177 ms 8428 KB Output is correct
18 Correct 172 ms 8348 KB Output is correct
19 Correct 179 ms 8508 KB Output is correct
20 Correct 173 ms 8436 KB Output is correct
21 Incorrect 1000 ms 13732 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 14072 KB Output is correct
2 Correct 938 ms 14044 KB Output is correct
3 Correct 940 ms 14100 KB Output is correct
4 Correct 967 ms 14156 KB Output is correct
5 Correct 975 ms 14188 KB Output is correct
6 Correct 763 ms 14076 KB Output is correct
7 Correct 760 ms 14196 KB Output is correct
8 Correct 761 ms 14076 KB Output is correct
9 Correct 764 ms 14172 KB Output is correct
10 Correct 728 ms 14148 KB Output is correct
11 Correct 745 ms 14216 KB Output is correct
12 Correct 738 ms 14080 KB Output is correct
13 Correct 744 ms 14308 KB Output is correct
14 Correct 724 ms 14072 KB Output is correct
15 Correct 744 ms 14200 KB Output is correct
16 Correct 167 ms 8292 KB Output is correct
17 Correct 177 ms 8428 KB Output is correct
18 Correct 172 ms 8348 KB Output is correct
19 Correct 179 ms 8508 KB Output is correct
20 Correct 173 ms 8436 KB Output is correct
21 Incorrect 1000 ms 13732 KB Output isn't correct
22 Halted 0 ms 0 KB -