답안 #43376 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43376	2018-03-15T05:12:47 Z	top34051	Boat (APIO16_boat)	C++14	58 / 100	1601 ms	25056 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++) {
	    int mx = 0;
        for(int j=1;j<=n;j++) if(a[j]<=itv[i].X && itv[i].Y<=b[j]) mx++;
        for(int cnt=1;cnt<=mx;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:92:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
boat.cpp:93: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	118 ms	20300 KB	Output is correct
2	Correct	118 ms	20376 KB	Output is correct
3	Correct	146 ms	20392 KB	Output is correct
4	Correct	117 ms	20568 KB	Output is correct
5	Correct	117 ms	20568 KB	Output is correct
6	Correct	117 ms	20568 KB	Output is correct
7	Correct	117 ms	20568 KB	Output is correct
8	Correct	116 ms	20568 KB	Output is correct
9	Correct	123 ms	20608 KB	Output is correct
10	Correct	119 ms	20608 KB	Output is correct
11	Correct	116 ms	20608 KB	Output is correct
12	Correct	118 ms	20608 KB	Output is correct
13	Correct	116 ms	20684 KB	Output is correct
14	Correct	126 ms	20684 KB	Output is correct
15	Correct	121 ms	20684 KB	Output is correct
16	Correct	29 ms	20684 KB	Output is correct
17	Correct	37 ms	20684 KB	Output is correct
18	Correct	30 ms	20684 KB	Output is correct
19	Correct	31 ms	20684 KB	Output is correct
20	Correct	30 ms	20684 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	118 ms	20300 KB	Output is correct
2	Correct	118 ms	20376 KB	Output is correct
3	Correct	146 ms	20392 KB	Output is correct
4	Correct	117 ms	20568 KB	Output is correct
5	Correct	117 ms	20568 KB	Output is correct
6	Correct	117 ms	20568 KB	Output is correct
7	Correct	117 ms	20568 KB	Output is correct
8	Correct	116 ms	20568 KB	Output is correct
9	Correct	123 ms	20608 KB	Output is correct
10	Correct	119 ms	20608 KB	Output is correct
11	Correct	116 ms	20608 KB	Output is correct
12	Correct	118 ms	20608 KB	Output is correct
13	Correct	116 ms	20684 KB	Output is correct
14	Correct	126 ms	20684 KB	Output is correct
15	Correct	121 ms	20684 KB	Output is correct
16	Correct	29 ms	20684 KB	Output is correct
17	Correct	37 ms	20684 KB	Output is correct
18	Correct	30 ms	20684 KB	Output is correct
19	Correct	31 ms	20684 KB	Output is correct
20	Correct	30 ms	20684 KB	Output is correct
21	Correct	930 ms	22344 KB	Output is correct
22	Correct	896 ms	22408 KB	Output is correct
23	Correct	811 ms	22408 KB	Output is correct
24	Correct	864 ms	22408 KB	Output is correct
25	Correct	861 ms	22408 KB	Output is correct
26	Correct	1381 ms	22676 KB	Output is correct
27	Correct	1429 ms	22820 KB	Output is correct
28	Correct	1396 ms	22820 KB	Output is correct
29	Correct	1371 ms	22820 KB	Output is correct
30	Correct	127 ms	22820 KB	Output is correct
31	Correct	127 ms	22820 KB	Output is correct
32	Correct	123 ms	22840 KB	Output is correct
33	Correct	124 ms	22840 KB	Output is correct
34	Correct	123 ms	22840 KB	Output is correct
35	Correct	127 ms	22840 KB	Output is correct
36	Correct	124 ms	22840 KB	Output is correct
37	Correct	126 ms	22840 KB	Output is correct
38	Correct	125 ms	22840 KB	Output is correct

Subtask #3
27.0 / 27.0

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

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	118 ms	20300 KB	Output is correct
2	Correct	118 ms	20376 KB	Output is correct
3	Correct	146 ms	20392 KB	Output is correct
4	Correct	117 ms	20568 KB	Output is correct
5	Correct	117 ms	20568 KB	Output is correct
6	Correct	117 ms	20568 KB	Output is correct
7	Correct	117 ms	20568 KB	Output is correct
8	Correct	116 ms	20568 KB	Output is correct
9	Correct	123 ms	20608 KB	Output is correct
10	Correct	119 ms	20608 KB	Output is correct
11	Correct	116 ms	20608 KB	Output is correct
12	Correct	118 ms	20608 KB	Output is correct
13	Correct	116 ms	20684 KB	Output is correct
14	Correct	126 ms	20684 KB	Output is correct
15	Correct	121 ms	20684 KB	Output is correct
16	Correct	29 ms	20684 KB	Output is correct
17	Correct	37 ms	20684 KB	Output is correct
18	Correct	30 ms	20684 KB	Output is correct
19	Correct	31 ms	20684 KB	Output is correct
20	Correct	30 ms	20684 KB	Output is correct
21	Correct	930 ms	22344 KB	Output is correct
22	Correct	896 ms	22408 KB	Output is correct
23	Correct	811 ms	22408 KB	Output is correct
24	Correct	864 ms	22408 KB	Output is correct
25	Correct	861 ms	22408 KB	Output is correct
26	Correct	1381 ms	22676 KB	Output is correct
27	Correct	1429 ms	22820 KB	Output is correct
28	Correct	1396 ms	22820 KB	Output is correct
29	Correct	1371 ms	22820 KB	Output is correct
30	Correct	127 ms	22820 KB	Output is correct
31	Correct	127 ms	22820 KB	Output is correct
32	Correct	123 ms	22840 KB	Output is correct
33	Correct	124 ms	22840 KB	Output is correct
34	Correct	123 ms	22840 KB	Output is correct
35	Correct	127 ms	22840 KB	Output is correct
36	Correct	124 ms	22840 KB	Output is correct
37	Correct	126 ms	22840 KB	Output is correct
38	Correct	125 ms	22840 KB	Output is correct
39	Correct	14 ms	22840 KB	Output is correct
40	Correct	13 ms	22840 KB	Output is correct
41	Correct	14 ms	22840 KB	Output is correct
42	Correct	13 ms	22840 KB	Output is correct
43	Correct	14 ms	22840 KB	Output is correct
44	Correct	18 ms	22840 KB	Output is correct
45	Correct	19 ms	22840 KB	Output is correct
46	Correct	18 ms	22840 KB	Output is correct
47	Correct	20 ms	22840 KB	Output is correct
48	Correct	19 ms	22840 KB	Output is correct
49	Correct	13 ms	22840 KB	Output is correct
50	Correct	12 ms	22840 KB	Output is correct
51	Correct	12 ms	22840 KB	Output is correct
52	Correct	12 ms	22840 KB	Output is correct
53	Correct	12 ms	22840 KB	Output is correct
54	Correct	10 ms	22840 KB	Output is correct
55	Correct	8 ms	22840 KB	Output is correct
56	Correct	9 ms	22840 KB	Output is correct
57	Correct	8 ms	22840 KB	Output is correct
58	Correct	9 ms	22840 KB	Output is correct
59	Correct	988 ms	24360 KB	Output is correct
60	Correct	920 ms	24360 KB	Output is correct
61	Correct	876 ms	24360 KB	Output is correct
62	Correct	1004 ms	24360 KB	Output is correct
63	Correct	956 ms	24360 KB	Output is correct
64	Correct	1571 ms	24944 KB	Output is correct
65	Correct	1568 ms	25056 KB	Output is correct
66	Correct	1561 ms	25056 KB	Output is correct
67	Correct	1556 ms	25056 KB	Output is correct
68	Correct	1601 ms	25056 KB	Output is correct
69	Correct	798 ms	25056 KB	Output is correct
70	Correct	792 ms	25056 KB	Output is correct
71	Correct	799 ms	25056 KB	Output is correct
72	Correct	824 ms	25056 KB	Output is correct
73	Correct	837 ms	25056 KB	Output is correct
74	Incorrect	196 ms	25056 KB	Output isn't correct
75	Halted	0 ms	0 KB	-

답안 #43376

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
0 / 42.0