답안 #43374 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43374	2018-03-15T04:48:23 Z	top34051	Boat (APIO16_boat)	C++14	36 / 100	2000 ms	26588 KB

boat

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define X first
#define Y second

const int maxn = 2e3 + 5;
const ll mod = 1e9 + 7;

int n,m;
int a[maxn], b[maxn];

vector<int> pos;
pii itv[maxn];
ll temp[maxn][maxn], comb[maxn][maxn];
ll rec[maxn][maxn];

ll dp[maxn][maxn];

ll fac[maxn], invfac[maxn];

ll add(ll x, ll y) { return ((x+y)%mod + mod)%mod; }

ll mul(ll x, ll y) { return ((x*y)%mod + mod)%mod; }

ll inv(ll x, ll y) { return 1<x ? y - inv(y%x, x)*y/x : 1; }

ll combi1(ll x, ll y) {
    return x<y ? 0 : mul(fac[x], mul(invfac[y], invfac[x-y]));
}

void init() {
	//get interval
	for(int i=1;i<=n;i++) {
		pos.push_back(a[i]);
		pos.push_back(b[i]+1);
	}
	sort(pos.begin(),pos.end());
	pos.erase(unique(pos.begin(),pos.end()),pos.end());
	for(int i=0;i<pos.size()-1;i++) itv[++m] = {pos[i],pos[i+1]-1};
//	for(int i=1;i<=m;i++) printf("[%d, %d] ",itv[i].X,itv[i].Y);
//	printf("\n");
	//fac and invfac
	fac[0] = 1; invfac[0] = inv(fac[0], mod);
//    printf("fac %d = %lld inv = %lld\n",1,fac[1],invfac[1]);
	for(int i=1;i<=m;i++) {
		fac[i] = mul(fac[i-1], i);
		invfac[i] = inv(fac[i], mod);
//		printf("fac %d = %lld inv = %lld\n",i,fac[i],invfac[i]);
	}
	for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) comb[i][j] = combi1(i,j);
	//precompute
	for(int i=1;i<=m;i++) {
        ll sz = itv[i].Y-itv[i].X+1;
        temp[i][1] = sz;
        for(int use=2;use<=n;use++) temp[i][use] = mul(temp[i][use-1], mul(sz-use+1, inv(use,mod)));
	}
//	printf("m = %d\n",m);
	for(int i=1;i<=m;i++) {
        for(int cnt=1;cnt<=n;cnt++) {
//            if(cnt==1) printf("calc %d %d\n",i,cnt);
        	for(int use=1;use<=cnt;use++) rec[i][cnt] = add(rec[i][cnt], mul(temp[i][use], comb[cnt-1][use-1]));
		}
	}
}

ll solve() {
    ll res = 0;
	for(int i=0;i<=m;i++) dp[0][i] = 1;
	for(int i=1;i<=m;i++) {
		for(int x=1;x<=n;x++) {
			dp[x][i] = dp[x][i-1];
			if(a[x]<=itv[i].X && itv[i].Y<=b[x]) {
				ll cnt = 1;
				for(int y=x-1;y>=0;y--) {
					dp[x][i] = add(dp[x][i], mul(dp[y][i-1], rec[i][cnt]));
					if(a[y]<=itv[i].X && itv[i].Y<=b[y]) cnt++;
				}
			}
//			printf("dp %d %d = %lld\n",x,i,dp[x][i]);
		}
	}
	for(int x=1;x<=n;x++) res = add(res, dp[x][m]);
	return res;
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
	init();
	printf("%lld",solve());
}

Compilation message

boat.cpp: In function 'void init()':
boat.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pos.size()-1;i++) itv[++m] = {pos[i],pos[i+1]-1};
               ^
boat.cpp: In function 'int main()':
boat.cpp:90:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
boat.cpp:91:49: 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1561 ms	26296 KB	Output is correct
2	Correct	1526 ms	26336 KB	Output is correct
3	Correct	1536 ms	26436 KB	Output is correct
4	Correct	1522 ms	26448 KB	Output is correct
5	Correct	1557 ms	26504 KB	Output is correct
6	Correct	1534 ms	26504 KB	Output is correct
7	Correct	1510 ms	26504 KB	Output is correct
8	Correct	1529 ms	26504 KB	Output is correct
9	Correct	1534 ms	26504 KB	Output is correct
10	Correct	1511 ms	26508 KB	Output is correct
11	Correct	1537 ms	26508 KB	Output is correct
12	Correct	1501 ms	26508 KB	Output is correct
13	Correct	1520 ms	26588 KB	Output is correct
14	Correct	1526 ms	26588 KB	Output is correct
15	Correct	1546 ms	26588 KB	Output is correct
16	Correct	291 ms	26588 KB	Output is correct
17	Correct	291 ms	26588 KB	Output is correct
18	Correct	279 ms	26588 KB	Output is correct
19	Correct	294 ms	26588 KB	Output is correct
20	Correct	283 ms	26588 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1561 ms	26296 KB	Output is correct
2	Correct	1526 ms	26336 KB	Output is correct
3	Correct	1536 ms	26436 KB	Output is correct
4	Correct	1522 ms	26448 KB	Output is correct
5	Correct	1557 ms	26504 KB	Output is correct
6	Correct	1534 ms	26504 KB	Output is correct
7	Correct	1510 ms	26504 KB	Output is correct
8	Correct	1529 ms	26504 KB	Output is correct
9	Correct	1534 ms	26504 KB	Output is correct
10	Correct	1511 ms	26508 KB	Output is correct
11	Correct	1537 ms	26508 KB	Output is correct
12	Correct	1501 ms	26508 KB	Output is correct
13	Correct	1520 ms	26588 KB	Output is correct
14	Correct	1526 ms	26588 KB	Output is correct
15	Correct	1546 ms	26588 KB	Output is correct
16	Correct	291 ms	26588 KB	Output is correct
17	Correct	291 ms	26588 KB	Output is correct
18	Correct	279 ms	26588 KB	Output is correct
19	Correct	294 ms	26588 KB	Output is correct
20	Correct	283 ms	26588 KB	Output is correct
21	Execution timed out	2013 ms	26588 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	26588 KB	Output is correct
2	Correct	22 ms	26588 KB	Output is correct
3	Correct	22 ms	26588 KB	Output is correct
4	Correct	22 ms	26588 KB	Output is correct
5	Correct	23 ms	26588 KB	Output is correct
6	Correct	32 ms	26588 KB	Output is correct
7	Correct	25 ms	26588 KB	Output is correct
8	Correct	28 ms	26588 KB	Output is correct
9	Correct	25 ms	26588 KB	Output is correct
10	Correct	25 ms	26588 KB	Output is correct
11	Correct	22 ms	26588 KB	Output is correct
12	Correct	23 ms	26588 KB	Output is correct
13	Correct	22 ms	26588 KB	Output is correct
14	Correct	21 ms	26588 KB	Output is correct
15	Correct	22 ms	26588 KB	Output is correct
16	Correct	17 ms	26588 KB	Output is correct
17	Correct	14 ms	26588 KB	Output is correct
18	Correct	15 ms	26588 KB	Output is correct
19	Correct	15 ms	26588 KB	Output is correct
20	Correct	17 ms	26588 KB	Output is correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1561 ms	26296 KB	Output is correct
2	Correct	1526 ms	26336 KB	Output is correct
3	Correct	1536 ms	26436 KB	Output is correct
4	Correct	1522 ms	26448 KB	Output is correct
5	Correct	1557 ms	26504 KB	Output is correct
6	Correct	1534 ms	26504 KB	Output is correct
7	Correct	1510 ms	26504 KB	Output is correct
8	Correct	1529 ms	26504 KB	Output is correct
9	Correct	1534 ms	26504 KB	Output is correct
10	Correct	1511 ms	26508 KB	Output is correct
11	Correct	1537 ms	26508 KB	Output is correct
12	Correct	1501 ms	26508 KB	Output is correct
13	Correct	1520 ms	26588 KB	Output is correct
14	Correct	1526 ms	26588 KB	Output is correct
15	Correct	1546 ms	26588 KB	Output is correct
16	Correct	291 ms	26588 KB	Output is correct
17	Correct	291 ms	26588 KB	Output is correct
18	Correct	279 ms	26588 KB	Output is correct
19	Correct	294 ms	26588 KB	Output is correct
20	Correct	283 ms	26588 KB	Output is correct
21	Execution timed out	2013 ms	26588 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

답안 #43374

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
0 / 42.0