답안 #261992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261992	2020-08-12T08:56:35 Z	amoo_safar	Boat (APIO16_boat)	C++17	100 / 100	1944 ms	4732 KB

boat

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> edge;
typedef pair<int, int> pii;

const int Maxn = 1e3 + 10;
const int Inf = 1e9;
const int Log = 20;
const int Mod = 1e9 + 7;

int mul(int a, int b){
	return (1ll * a * b) % Mod;
}

int pw(int b, int p){
	if(p == 0) return 1;
	if(p & 1) return mul(b, pw(b, p - 1));
	return pw(mul(b, b), p >> 1);
}
int inv[Maxn * 4];

int a[Maxn], b[Maxn];
set<int> st;
vector<pii> V;

int dp[2][1040][510];
int sm[2][1040];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int i = 0; i < 4 * Maxn; i++) inv[i] = pw(i, Mod - 2);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		b[i] ++;
		st.insert(a[i]);
		st.insert(b[i]);
		//assert(a[i] == b[i] - 1);
	}
	
	ll l = -1;
	for(auto x : st){
		if(l != -1) V.pb({l, x});
		l = x;
	}
	sort(all(V));
	int m = V.size();
	for(int I = 1; I <= n; I++){
		int II = I & 1;
		memset(dp[II], 0, sizeof dp[II]);
		memset(sm[II], 0, sizeof sm[II]);
		
		for(int i = 0; i < m; i++){
			if( (a[I] <= V[i].F) && (V[i].S <= b[I]) ){
				for(int cnt = 2; cnt <= I; cnt ++){
					//if(cnt > V[i].S - V[i].F) continue;
					dp[II][i][cnt] = mul( dp[II ^ 1][i][cnt - 1], mul((V[i].S - V[i].F) - cnt + 1, inv[cnt]) );
				}
			}
			if( (a[I] <= V[i].F) && (V[i].S <= b[I]) ){
				for(int j = 0; j < i; j++){
					dp[II][i][1] += mul( sm[II ^ 1][j], V[i].S - V[i].F );
					if(dp[II][i][1] >= Mod)
						dp[II][i][1] %= Mod;
				}
			}
		}
		
		for(int i = 0; i < m; i++){
			if( (a[I] <= V[i].F) && (V[i].S <= b[I]) ){
				dp[II][i][1] += (V[i].S - V[i].F);
				//S += (V[i].S - V[i].F);
				dp[II][i][1] %= Mod;
			}
		}
		
		for(int i = 0; i < m; i++) for(int cnt = 1; cnt <= I; cnt ++){
			dp[II][i][cnt] += dp[II ^ 1][i][cnt];
			if(dp[II][i][cnt] >= Mod)
				dp[II][i][cnt] -= Mod;
			
		}
		
		for(int i = 0; i < m; i++) for(int cnt = 1; cnt <= I; cnt ++){
			sm[II][i] += dp[II][i][cnt];
			//cerr << I << " " << dp[II][i][cnt] << "\n";
			//sm[II][i] %= Mod;
			if(sm[II][i] >= Mod)
				sm[II][i] -= Mod;
		}
	}
	
	ll ans = 0;
	for(int i = 0; i < m; i++) ans += sm[n & 1][i];
	cout << ((ans % Mod) + Mod) % Mod << '\n';
	return 0;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	408 ms	4608 KB	Output is correct
2	Correct	405 ms	4608 KB	Output is correct
3	Correct	394 ms	4608 KB	Output is correct
4	Correct	398 ms	4728 KB	Output is correct
5	Correct	409 ms	4728 KB	Output is correct
6	Correct	432 ms	4644 KB	Output is correct
7	Correct	398 ms	4728 KB	Output is correct
8	Correct	401 ms	4608 KB	Output is correct
9	Correct	408 ms	4640 KB	Output is correct
10	Correct	404 ms	4640 KB	Output is correct
11	Correct	407 ms	4644 KB	Output is correct
12	Correct	407 ms	4608 KB	Output is correct
13	Correct	411 ms	4608 KB	Output is correct
14	Correct	406 ms	4608 KB	Output is correct
15	Correct	413 ms	4608 KB	Output is correct
16	Correct	122 ms	4480 KB	Output is correct
17	Correct	142 ms	4480 KB	Output is correct
18	Correct	124 ms	4600 KB	Output is correct
19	Correct	118 ms	4480 KB	Output is correct
20	Correct	120 ms	4600 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	408 ms	4608 KB	Output is correct
2	Correct	405 ms	4608 KB	Output is correct
3	Correct	394 ms	4608 KB	Output is correct
4	Correct	398 ms	4728 KB	Output is correct
5	Correct	409 ms	4728 KB	Output is correct
6	Correct	432 ms	4644 KB	Output is correct
7	Correct	398 ms	4728 KB	Output is correct
8	Correct	401 ms	4608 KB	Output is correct
9	Correct	408 ms	4640 KB	Output is correct
10	Correct	404 ms	4640 KB	Output is correct
11	Correct	407 ms	4644 KB	Output is correct
12	Correct	407 ms	4608 KB	Output is correct
13	Correct	411 ms	4608 KB	Output is correct
14	Correct	406 ms	4608 KB	Output is correct
15	Correct	413 ms	4608 KB	Output is correct
16	Correct	122 ms	4480 KB	Output is correct
17	Correct	142 ms	4480 KB	Output is correct
18	Correct	124 ms	4600 KB	Output is correct
19	Correct	118 ms	4480 KB	Output is correct
20	Correct	120 ms	4600 KB	Output is correct
21	Correct	1090 ms	4728 KB	Output is correct
22	Correct	1060 ms	4728 KB	Output is correct
23	Correct	1047 ms	4728 KB	Output is correct
24	Correct	1020 ms	4728 KB	Output is correct
25	Correct	1037 ms	4728 KB	Output is correct
26	Correct	1290 ms	4636 KB	Output is correct
27	Correct	1350 ms	4728 KB	Output is correct
28	Correct	1402 ms	4632 KB	Output is correct
29	Correct	1331 ms	4608 KB	Output is correct
30	Correct	418 ms	4728 KB	Output is correct
31	Correct	407 ms	4608 KB	Output is correct
32	Correct	413 ms	4608 KB	Output is correct
33	Correct	409 ms	4728 KB	Output is correct
34	Correct	416 ms	4728 KB	Output is correct
35	Correct	402 ms	4608 KB	Output is correct
36	Correct	409 ms	4648 KB	Output is correct
37	Correct	403 ms	4608 KB	Output is correct
38	Correct	415 ms	4608 KB	Output is correct

Subtask #3
27.0 / 27.0

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

Subtask #4
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	408 ms	4608 KB	Output is correct
2	Correct	405 ms	4608 KB	Output is correct
3	Correct	394 ms	4608 KB	Output is correct
4	Correct	398 ms	4728 KB	Output is correct
5	Correct	409 ms	4728 KB	Output is correct
6	Correct	432 ms	4644 KB	Output is correct
7	Correct	398 ms	4728 KB	Output is correct
8	Correct	401 ms	4608 KB	Output is correct
9	Correct	408 ms	4640 KB	Output is correct
10	Correct	404 ms	4640 KB	Output is correct
11	Correct	407 ms	4644 KB	Output is correct
12	Correct	407 ms	4608 KB	Output is correct
13	Correct	411 ms	4608 KB	Output is correct
14	Correct	406 ms	4608 KB	Output is correct
15	Correct	413 ms	4608 KB	Output is correct
16	Correct	122 ms	4480 KB	Output is correct
17	Correct	142 ms	4480 KB	Output is correct
18	Correct	124 ms	4600 KB	Output is correct
19	Correct	118 ms	4480 KB	Output is correct
20	Correct	120 ms	4600 KB	Output is correct
21	Correct	1090 ms	4728 KB	Output is correct
22	Correct	1060 ms	4728 KB	Output is correct
23	Correct	1047 ms	4728 KB	Output is correct
24	Correct	1020 ms	4728 KB	Output is correct
25	Correct	1037 ms	4728 KB	Output is correct
26	Correct	1290 ms	4636 KB	Output is correct
27	Correct	1350 ms	4728 KB	Output is correct
28	Correct	1402 ms	4632 KB	Output is correct
29	Correct	1331 ms	4608 KB	Output is correct
30	Correct	418 ms	4728 KB	Output is correct
31	Correct	407 ms	4608 KB	Output is correct
32	Correct	413 ms	4608 KB	Output is correct
33	Correct	409 ms	4728 KB	Output is correct
34	Correct	416 ms	4728 KB	Output is correct
35	Correct	402 ms	4608 KB	Output is correct
36	Correct	409 ms	4648 KB	Output is correct
37	Correct	403 ms	4608 KB	Output is correct
38	Correct	415 ms	4608 KB	Output is correct
39	Correct	23 ms	4480 KB	Output is correct
40	Correct	23 ms	4600 KB	Output is correct
41	Correct	23 ms	4608 KB	Output is correct
42	Correct	23 ms	4480 KB	Output is correct
43	Correct	24 ms	4480 KB	Output is correct
44	Correct	27 ms	4480 KB	Output is correct
45	Correct	27 ms	4480 KB	Output is correct
46	Correct	27 ms	4480 KB	Output is correct
47	Correct	27 ms	4480 KB	Output is correct
48	Correct	27 ms	4480 KB	Output is correct
49	Correct	25 ms	4608 KB	Output is correct
50	Correct	31 ms	4480 KB	Output is correct
51	Correct	23 ms	4480 KB	Output is correct
52	Correct	23 ms	4480 KB	Output is correct
53	Correct	24 ms	4480 KB	Output is correct
54	Correct	17 ms	4480 KB	Output is correct
55	Correct	17 ms	4480 KB	Output is correct
56	Correct	17 ms	4480 KB	Output is correct
57	Correct	19 ms	4480 KB	Output is correct
58	Correct	18 ms	4480 KB	Output is correct
59	Correct	1463 ms	4728 KB	Output is correct
60	Correct	1365 ms	4728 KB	Output is correct
61	Correct	1344 ms	4648 KB	Output is correct
62	Correct	1473 ms	4644 KB	Output is correct
63	Correct	1399 ms	4728 KB	Output is correct
64	Correct	1925 ms	4732 KB	Output is correct
65	Correct	1944 ms	4608 KB	Output is correct
66	Correct	1867 ms	4644 KB	Output is correct
67	Correct	1889 ms	4608 KB	Output is correct
68	Correct	1921 ms	4644 KB	Output is correct
69	Correct	1323 ms	4608 KB	Output is correct
70	Correct	1316 ms	4732 KB	Output is correct
71	Correct	1329 ms	4728 KB	Output is correct
72	Correct	1380 ms	4728 KB	Output is correct
73	Correct	1352 ms	4648 KB	Output is correct
74	Correct	193 ms	4480 KB	Output is correct
75	Correct	187 ms	4480 KB	Output is correct
76	Correct	182 ms	4480 KB	Output is correct
77	Correct	182 ms	4480 KB	Output is correct
78	Correct	173 ms	4480 KB	Output is correct

답안 #261992

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