답안 #447803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447803	2021-07-27T14:48:57 Z	dutch	Boat (APIO16_boat)	C++17	100 / 100	1503 ms	4424 KB

boat

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define valid(x, y) (a[x] <= pts[y] && pts[y+1] <= b[x]+1)

const int MOD = 1e9+7, LIM = 501;

int modInverse(int x){
	int r = 1, p = (MOD - 2) * 2;
	for(int y=x; p/=2; y=(y*y) % MOD)
		if(p & 1) r = (r*y) % MOD;
	return r;
}

int n, a[LIM], b[LIM], dp[LIM][LIM*2], F[LIM], invF[LIM], C[LIM];
vector<int> pts;

int nCr(int x, int y){
	return (((F[x] * invF[y]) % MOD) * invF[x-y]) % MOD;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);

	cin >> n;
	for(int i=0; i<n; ++i){
		cin >> a[i] >> b[i];
		pts.push_back(a[i]);
		pts.push_back(b[i]+1);
	}
	sort(pts.begin(), pts.end());
	pts.resize(unique(pts.begin(), pts.end()) - pts.begin());

	int m = size(pts) - 1, ans = 0;

	F[0] = invF[0] = 1;
	for(int i=1; i<=n; ++i){
		F[i] = (F[i-1] * i) % MOD;
		invF[i] = modInverse(F[i]);
	}
	for(int k=0; k<m; ++k){
		int diff = pts[k+1] - pts[k];
		for(int i=1; i<=n; ++i){
			int p = 1; C[i] = 0;
			for(int j=1; j<=i; ++j){
				(p *= diff - j + 1) %= MOD;
				C[i] += ((p * invF[j]) % MOD) * nCr(i-1, j-1);
				C[i] %= MOD;
			}
		}
		for(int i=0; i<n; ++i){
			if(!valid(i, k)) continue;
			int cnt = 1;
			for(int j=i; --j>=0; ){
				if(k) (dp[i][k] += dp[j][k-1] * C[cnt]) %= MOD;
				cnt += valid(j, k);
			}
			(dp[i][k] += C[cnt]) %= MOD;
			(ans += dp[i][k]) %= MOD;
		}
		for(int i=0; i<n; ++i){
			(dp[i][k] += dp[i][k-1]) %= MOD;
		}
	}
	cout << (ans % MOD + MOD) % MOD;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1167 ms	4424 KB	Output is correct
2	Correct	1175 ms	4344 KB	Output is correct
3	Correct	1178 ms	4264 KB	Output is correct
4	Correct	1179 ms	4344 KB	Output is correct
5	Correct	1171 ms	4268 KB	Output is correct
6	Correct	1174 ms	4380 KB	Output is correct
7	Correct	1187 ms	4236 KB	Output is correct
8	Correct	1167 ms	4284 KB	Output is correct
9	Correct	1167 ms	4272 KB	Output is correct
10	Correct	1163 ms	4188 KB	Output is correct
11	Correct	1171 ms	4268 KB	Output is correct
12	Correct	1169 ms	4292 KB	Output is correct
13	Correct	1171 ms	4364 KB	Output is correct
14	Correct	1161 ms	4316 KB	Output is correct
15	Correct	1171 ms	4324 KB	Output is correct
16	Correct	209 ms	3020 KB	Output is correct
17	Correct	222 ms	2968 KB	Output is correct
18	Correct	217 ms	3020 KB	Output is correct
19	Correct	224 ms	3052 KB	Output is correct
20	Correct	214 ms	3012 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1167 ms	4424 KB	Output is correct
2	Correct	1175 ms	4344 KB	Output is correct
3	Correct	1178 ms	4264 KB	Output is correct
4	Correct	1179 ms	4344 KB	Output is correct
5	Correct	1171 ms	4268 KB	Output is correct
6	Correct	1174 ms	4380 KB	Output is correct
7	Correct	1187 ms	4236 KB	Output is correct
8	Correct	1167 ms	4284 KB	Output is correct
9	Correct	1167 ms	4272 KB	Output is correct
10	Correct	1163 ms	4188 KB	Output is correct
11	Correct	1171 ms	4268 KB	Output is correct
12	Correct	1169 ms	4292 KB	Output is correct
13	Correct	1171 ms	4364 KB	Output is correct
14	Correct	1161 ms	4316 KB	Output is correct
15	Correct	1171 ms	4324 KB	Output is correct
16	Correct	209 ms	3020 KB	Output is correct
17	Correct	222 ms	2968 KB	Output is correct
18	Correct	217 ms	3020 KB	Output is correct
19	Correct	224 ms	3052 KB	Output is correct
20	Correct	214 ms	3012 KB	Output is correct
21	Correct	1276 ms	4364 KB	Output is correct
22	Correct	1276 ms	4304 KB	Output is correct
23	Correct	1242 ms	4264 KB	Output is correct
24	Correct	1244 ms	4412 KB	Output is correct
25	Correct	1245 ms	4356 KB	Output is correct
26	Correct	1309 ms	4364 KB	Output is correct
27	Correct	1327 ms	4264 KB	Output is correct
28	Correct	1308 ms	4164 KB	Output is correct
29	Correct	1291 ms	4360 KB	Output is correct
30	Correct	1164 ms	4340 KB	Output is correct
31	Correct	1174 ms	4292 KB	Output is correct
32	Correct	1157 ms	4268 KB	Output is correct
33	Correct	1167 ms	4292 KB	Output is correct
34	Correct	1166 ms	4376 KB	Output is correct
35	Correct	1176 ms	4344 KB	Output is correct
36	Correct	1166 ms	4328 KB	Output is correct
37	Correct	1174 ms	4268 KB	Output is correct
38	Correct	1163 ms	4300 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	844 KB	Output is correct
2	Correct	12 ms	876 KB	Output is correct
3	Correct	12 ms	844 KB	Output is correct
4	Correct	12 ms	868 KB	Output is correct
5	Correct	14 ms	780 KB	Output is correct
6	Correct	13 ms	824 KB	Output is correct
7	Correct	13 ms	844 KB	Output is correct
8	Correct	13 ms	844 KB	Output is correct
9	Correct	14 ms	832 KB	Output is correct
10	Correct	13 ms	812 KB	Output is correct
11	Correct	12 ms	844 KB	Output is correct
12	Correct	12 ms	888 KB	Output is correct
13	Correct	12 ms	808 KB	Output is correct
14	Correct	12 ms	848 KB	Output is correct
15	Correct	12 ms	844 KB	Output is correct
16	Correct	7 ms	792 KB	Output is correct
17	Correct	7 ms	716 KB	Output is correct
18	Correct	8 ms	716 KB	Output is correct
19	Correct	7 ms	716 KB	Output is correct
20	Correct	7 ms	792 KB	Output is correct

Subtask #4
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1167 ms	4424 KB	Output is correct
2	Correct	1175 ms	4344 KB	Output is correct
3	Correct	1178 ms	4264 KB	Output is correct
4	Correct	1179 ms	4344 KB	Output is correct
5	Correct	1171 ms	4268 KB	Output is correct
6	Correct	1174 ms	4380 KB	Output is correct
7	Correct	1187 ms	4236 KB	Output is correct
8	Correct	1167 ms	4284 KB	Output is correct
9	Correct	1167 ms	4272 KB	Output is correct
10	Correct	1163 ms	4188 KB	Output is correct
11	Correct	1171 ms	4268 KB	Output is correct
12	Correct	1169 ms	4292 KB	Output is correct
13	Correct	1171 ms	4364 KB	Output is correct
14	Correct	1161 ms	4316 KB	Output is correct
15	Correct	1171 ms	4324 KB	Output is correct
16	Correct	209 ms	3020 KB	Output is correct
17	Correct	222 ms	2968 KB	Output is correct
18	Correct	217 ms	3020 KB	Output is correct
19	Correct	224 ms	3052 KB	Output is correct
20	Correct	214 ms	3012 KB	Output is correct
21	Correct	1276 ms	4364 KB	Output is correct
22	Correct	1276 ms	4304 KB	Output is correct
23	Correct	1242 ms	4264 KB	Output is correct
24	Correct	1244 ms	4412 KB	Output is correct
25	Correct	1245 ms	4356 KB	Output is correct
26	Correct	1309 ms	4364 KB	Output is correct
27	Correct	1327 ms	4264 KB	Output is correct
28	Correct	1308 ms	4164 KB	Output is correct
29	Correct	1291 ms	4360 KB	Output is correct
30	Correct	1164 ms	4340 KB	Output is correct
31	Correct	1174 ms	4292 KB	Output is correct
32	Correct	1157 ms	4268 KB	Output is correct
33	Correct	1167 ms	4292 KB	Output is correct
34	Correct	1166 ms	4376 KB	Output is correct
35	Correct	1176 ms	4344 KB	Output is correct
36	Correct	1166 ms	4328 KB	Output is correct
37	Correct	1174 ms	4268 KB	Output is correct
38	Correct	1163 ms	4300 KB	Output is correct
39	Correct	12 ms	844 KB	Output is correct
40	Correct	12 ms	876 KB	Output is correct
41	Correct	12 ms	844 KB	Output is correct
42	Correct	12 ms	868 KB	Output is correct
43	Correct	14 ms	780 KB	Output is correct
44	Correct	13 ms	824 KB	Output is correct
45	Correct	13 ms	844 KB	Output is correct
46	Correct	13 ms	844 KB	Output is correct
47	Correct	14 ms	832 KB	Output is correct
48	Correct	13 ms	812 KB	Output is correct
49	Correct	12 ms	844 KB	Output is correct
50	Correct	12 ms	888 KB	Output is correct
51	Correct	12 ms	808 KB	Output is correct
52	Correct	12 ms	848 KB	Output is correct
53	Correct	12 ms	844 KB	Output is correct
54	Correct	7 ms	792 KB	Output is correct
55	Correct	7 ms	716 KB	Output is correct
56	Correct	8 ms	716 KB	Output is correct
57	Correct	7 ms	716 KB	Output is correct
58	Correct	7 ms	792 KB	Output is correct
59	Correct	1391 ms	4264 KB	Output is correct
60	Correct	1375 ms	4392 KB	Output is correct
61	Correct	1361 ms	4392 KB	Output is correct
62	Correct	1392 ms	4420 KB	Output is correct
63	Correct	1398 ms	4264 KB	Output is correct
64	Correct	1488 ms	4272 KB	Output is correct
65	Correct	1478 ms	4308 KB	Output is correct
66	Correct	1471 ms	4332 KB	Output is correct
67	Correct	1485 ms	4340 KB	Output is correct
68	Correct	1503 ms	4420 KB	Output is correct
69	Correct	1332 ms	4360 KB	Output is correct
70	Correct	1330 ms	4292 KB	Output is correct
71	Correct	1324 ms	4280 KB	Output is correct
72	Correct	1343 ms	4320 KB	Output is correct
73	Correct	1337 ms	4304 KB	Output is correct
74	Correct	250 ms	3012 KB	Output is correct
75	Correct	268 ms	3048 KB	Output is correct
76	Correct	256 ms	3016 KB	Output is correct
77	Correct	259 ms	3064 KB	Output is correct
78	Correct	251 ms	3012 KB	Output is correct

답안 #447803

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 42.0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
42.0 / 42.0