oj.uz

Submission #113370

# Submission time Handle Problem Language Result Execution time Memory
113370 2019-05-25T09:05:24 Z 임유진(#2858) Boat (APIO16_boat) C++14
9 / 100
 940 ms 14316 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][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<=N; 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 899 ms 14072 KB Output is correct
2 Correct 940 ms 14212 KB Output is correct
3 Correct 915 ms 14316 KB Output is correct
4 Correct 904 ms 14072 KB Output is correct
5 Correct 896 ms 13976 KB Output is correct
6 Correct 734 ms 14084 KB Output is correct
7 Correct 757 ms 14072 KB Output is correct
8 Correct 749 ms 14072 KB Output is correct
9 Correct 744 ms 14192 KB Output is correct
10 Correct 750 ms 14072 KB Output is correct
11 Correct 818 ms 14200 KB Output is correct
12 Correct 794 ms 14072 KB Output is correct
13 Correct 740 ms 14072 KB Output is correct
14 Correct 742 ms 14116 KB Output is correct
15 Correct 759 ms 14212 KB Output is correct
16 Correct 172 ms 8424 KB Output is correct
17 Correct 181 ms 8440 KB Output is correct
18 Correct 183 ms 8412 KB Output is correct
19 Correct 179 ms 8480 KB Output is correct
20 Correct 176 ms 8456 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 14072 KB Output is correct
2 Correct 940 ms 14212 KB Output is correct
3 Correct 915 ms 14316 KB Output is correct
4 Correct 904 ms 14072 KB Output is correct
5 Correct 896 ms 13976 KB Output is correct
6 Correct 734 ms 14084 KB Output is correct
7 Correct 757 ms 14072 KB Output is correct
8 Correct 749 ms 14072 KB Output is correct
9 Correct 744 ms 14192 KB Output is correct
10 Correct 750 ms 14072 KB Output is correct
11 Correct 818 ms 14200 KB Output is correct
12 Correct 794 ms 14072 KB Output is correct
13 Correct 740 ms 14072 KB Output is correct
14 Correct 742 ms 14116 KB Output is correct
15 Correct 759 ms 14212 KB Output is correct
16 Correct 172 ms 8424 KB Output is correct
17 Correct 181 ms 8440 KB Output is correct
18 Correct 183 ms 8412 KB Output is correct
19 Correct 179 ms 8480 KB Output is correct
20 Correct 176 ms 8456 KB Output is correct
21 Incorrect 913 ms 13720 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 14072 KB Output is correct
2 Correct 940 ms 14212 KB Output is correct
3 Correct 915 ms 14316 KB Output is correct
4 Correct 904 ms 14072 KB Output is correct
5 Correct 896 ms 13976 KB Output is correct
6 Correct 734 ms 14084 KB Output is correct
7 Correct 757 ms 14072 KB Output is correct
8 Correct 749 ms 14072 KB Output is correct
9 Correct 744 ms 14192 KB Output is correct
10 Correct 750 ms 14072 KB Output is correct
11 Correct 818 ms 14200 KB Output is correct
12 Correct 794 ms 14072 KB Output is correct
13 Correct 740 ms 14072 KB Output is correct
14 Correct 742 ms 14116 KB Output is correct
15 Correct 759 ms 14212 KB Output is correct
16 Correct 172 ms 8424 KB Output is correct
17 Correct 181 ms 8440 KB Output is correct
18 Correct 183 ms 8412 KB Output is correct
19 Correct 179 ms 8480 KB Output is correct
20 Correct 176 ms 8456 KB Output is correct
21 Incorrect 913 ms 13720 KB Output isn't correct
22 Halted 0 ms 0 KB -