답안 #376285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376285	2021-03-11T07:25:05 Z	shivensinha4	Boat (APIO16_boat)	C++17	58 / 100	2000 ms	16364 KB

boat

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
// #define endl '\n'
 
const ll mod = 1e9+7;
 
ll power(ll x, ll y) {
	if (y == 0) return 1;
	ll p = power(x, y/2) % mod;
	p = (p * p) % mod;
  
	return (y%2 == 0)? p : (x * p) % mod;
}
 
ll modInverse(ll a) {
	return power(a, mod-2);
}
 
const int MXN = 500;
ll choose[4*MXN+2][MXN+1], dp[2][MXN+1][MXN+1][2];
 
int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin >> n;
	vector<ii> lt(n);
	vi raw(2*n);
	
	for_(i, 0, n) {
		cin >> lt[i][0] >> lt[i][1];
		raw[2*i] = lt[i][0], raw[2*i+1] = lt[i][1];
	}
	
	sort(raw.begin(), raw.end());
	raw.resize(unique(raw.begin(), raw.end()) - raw.begin());
	
	vector<ii> seg;
	int pre = -1;
	for_(i, 0, raw.size()) {
		if (pre < raw[i] and pre != -1) seg.push_back({pre, raw[i]-1});
		seg.push_back({raw[i], raw[i]});
		pre = raw[i]+1;
	}
	
	int ns = seg.size();
	// cout << ns << endl;
	memset(choose, 0, sizeof(choose)); memset(dp, 0, sizeof(dp));
	
	vector<ll> modInv(n+1);
	for_(i, 1, n+1) modInv[i] = modInverse(i);
	
	for_(i, 0, ns) {
		choose[i][0] = 1;
		for_(r, 1, min(n, seg[i][1]-seg[i][0]+1) + 1) choose[i][r] = (((choose[i][r-1] * (seg[i][1]-seg[i][0]-r+2)) % mod) * modInv[r]) % mod;
	}
	
	int c = 0;
	for (int s = ns-1; s >= 0; s--) {
		memset(dp[c], 0, sizeof(dp[c]));
		
		for (int ct = min(n-1, seg[s][1]-seg[s][0]+1); ct >= 0; ct--) {
			dp[c][ct][n][0] = choose[s][ct];
			
			for (int idx = n-1; idx >= 0; idx--) {
				if (seg[s][0] >= lt[idx][0] and seg[s][1] <= lt[idx][1]) dp[c][ct][idx][1] += dp[c][ct+1][idx+1][0];
				if (dp[c][ct][idx][1] >= mod) dp[c][ct][idx][1] -= mod;
				
				dp[c][ct][idx][1] += (choose[s][ct] * (s < ns-1 ? dp[1-c][0][idx][1] : 0)) % mod;
				if (dp[c][ct][idx][1] >= mod) dp[c][ct][idx][1] -= mod;
				
				dp[c][ct][idx][0] = dp[c][ct][idx][1] + dp[c][ct][idx+1][0];
				if (dp[c][ct][idx][0] >= mod) dp[c][ct][idx][0] -= mod;
			}
		}
		c = 1-c;
	}
	
	cout << (dp[1-c][0][0][0]-1+mod) % mod << endl;
	
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1203 ms	16236 KB	Output is correct
2	Correct	1210 ms	16236 KB	Output is correct
3	Correct	1200 ms	16236 KB	Output is correct
4	Correct	1230 ms	16128 KB	Output is correct
5	Correct	1220 ms	16236 KB	Output is correct
6	Correct	994 ms	16236 KB	Output is correct
7	Correct	970 ms	16364 KB	Output is correct
8	Correct	1004 ms	16108 KB	Output is correct
9	Correct	1006 ms	16236 KB	Output is correct
10	Correct	985 ms	16108 KB	Output is correct
11	Correct	1016 ms	16236 KB	Output is correct
12	Correct	1014 ms	16236 KB	Output is correct
13	Correct	1022 ms	16236 KB	Output is correct
14	Correct	977 ms	16128 KB	Output is correct
15	Correct	1020 ms	16236 KB	Output is correct
16	Correct	220 ms	16120 KB	Output is correct
17	Correct	230 ms	16108 KB	Output is correct
18	Correct	217 ms	16108 KB	Output is correct
19	Correct	239 ms	16108 KB	Output is correct
20	Correct	223 ms	16108 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1203 ms	16236 KB	Output is correct
2	Correct	1210 ms	16236 KB	Output is correct
3	Correct	1200 ms	16236 KB	Output is correct
4	Correct	1230 ms	16128 KB	Output is correct
5	Correct	1220 ms	16236 KB	Output is correct
6	Correct	994 ms	16236 KB	Output is correct
7	Correct	970 ms	16364 KB	Output is correct
8	Correct	1004 ms	16108 KB	Output is correct
9	Correct	1006 ms	16236 KB	Output is correct
10	Correct	985 ms	16108 KB	Output is correct
11	Correct	1016 ms	16236 KB	Output is correct
12	Correct	1014 ms	16236 KB	Output is correct
13	Correct	1022 ms	16236 KB	Output is correct
14	Correct	977 ms	16128 KB	Output is correct
15	Correct	1020 ms	16236 KB	Output is correct
16	Correct	220 ms	16120 KB	Output is correct
17	Correct	230 ms	16108 KB	Output is correct
18	Correct	217 ms	16108 KB	Output is correct
19	Correct	239 ms	16108 KB	Output is correct
20	Correct	223 ms	16108 KB	Output is correct
21	Correct	668 ms	16108 KB	Output is correct
22	Correct	686 ms	16108 KB	Output is correct
23	Correct	700 ms	16236 KB	Output is correct
24	Correct	710 ms	16236 KB	Output is correct
25	Correct	678 ms	16236 KB	Output is correct
26	Correct	650 ms	16236 KB	Output is correct
27	Correct	634 ms	16152 KB	Output is correct
28	Correct	673 ms	16236 KB	Output is correct
29	Correct	671 ms	16152 KB	Output is correct
30	Correct	1279 ms	16156 KB	Output is correct
31	Correct	1282 ms	16108 KB	Output is correct
32	Correct	1224 ms	16144 KB	Output is correct
33	Correct	1299 ms	16236 KB	Output is correct
34	Correct	1420 ms	16144 KB	Output is correct
35	Correct	1206 ms	16128 KB	Output is correct
36	Correct	1205 ms	16128 KB	Output is correct
37	Correct	1281 ms	16236 KB	Output is correct
38	Correct	1174 ms	16236 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	186 ms	16108 KB	Output is correct
2	Correct	164 ms	16108 KB	Output is correct
3	Correct	175 ms	16108 KB	Output is correct
4	Correct	214 ms	16108 KB	Output is correct
5	Correct	174 ms	16108 KB	Output is correct
6	Correct	201 ms	16108 KB	Output is correct
7	Correct	196 ms	16108 KB	Output is correct
8	Correct	219 ms	16108 KB	Output is correct
9	Correct	183 ms	16108 KB	Output is correct
10	Correct	174 ms	16108 KB	Output is correct
11	Correct	173 ms	16108 KB	Output is correct
12	Correct	184 ms	16108 KB	Output is correct
13	Correct	163 ms	16108 KB	Output is correct
14	Correct	170 ms	16108 KB	Output is correct
15	Correct	193 ms	16108 KB	Output is correct
16	Correct	88 ms	16108 KB	Output is correct
17	Correct	85 ms	16108 KB	Output is correct
18	Correct	90 ms	16108 KB	Output is correct
19	Correct	90 ms	16256 KB	Output is correct
20	Correct	93 ms	16108 KB	Output is correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1203 ms	16236 KB	Output is correct
2	Correct	1210 ms	16236 KB	Output is correct
3	Correct	1200 ms	16236 KB	Output is correct
4	Correct	1230 ms	16128 KB	Output is correct
5	Correct	1220 ms	16236 KB	Output is correct
6	Correct	994 ms	16236 KB	Output is correct
7	Correct	970 ms	16364 KB	Output is correct
8	Correct	1004 ms	16108 KB	Output is correct
9	Correct	1006 ms	16236 KB	Output is correct
10	Correct	985 ms	16108 KB	Output is correct
11	Correct	1016 ms	16236 KB	Output is correct
12	Correct	1014 ms	16236 KB	Output is correct
13	Correct	1022 ms	16236 KB	Output is correct
14	Correct	977 ms	16128 KB	Output is correct
15	Correct	1020 ms	16236 KB	Output is correct
16	Correct	220 ms	16120 KB	Output is correct
17	Correct	230 ms	16108 KB	Output is correct
18	Correct	217 ms	16108 KB	Output is correct
19	Correct	239 ms	16108 KB	Output is correct
20	Correct	223 ms	16108 KB	Output is correct
21	Correct	668 ms	16108 KB	Output is correct
22	Correct	686 ms	16108 KB	Output is correct
23	Correct	700 ms	16236 KB	Output is correct
24	Correct	710 ms	16236 KB	Output is correct
25	Correct	678 ms	16236 KB	Output is correct
26	Correct	650 ms	16236 KB	Output is correct
27	Correct	634 ms	16152 KB	Output is correct
28	Correct	673 ms	16236 KB	Output is correct
29	Correct	671 ms	16152 KB	Output is correct
30	Correct	1279 ms	16156 KB	Output is correct
31	Correct	1282 ms	16108 KB	Output is correct
32	Correct	1224 ms	16144 KB	Output is correct
33	Correct	1299 ms	16236 KB	Output is correct
34	Correct	1420 ms	16144 KB	Output is correct
35	Correct	1206 ms	16128 KB	Output is correct
36	Correct	1205 ms	16128 KB	Output is correct
37	Correct	1281 ms	16236 KB	Output is correct
38	Correct	1174 ms	16236 KB	Output is correct
39	Correct	186 ms	16108 KB	Output is correct
40	Correct	164 ms	16108 KB	Output is correct
41	Correct	175 ms	16108 KB	Output is correct
42	Correct	214 ms	16108 KB	Output is correct
43	Correct	174 ms	16108 KB	Output is correct
44	Correct	201 ms	16108 KB	Output is correct
45	Correct	196 ms	16108 KB	Output is correct
46	Correct	219 ms	16108 KB	Output is correct
47	Correct	183 ms	16108 KB	Output is correct
48	Correct	174 ms	16108 KB	Output is correct
49	Correct	173 ms	16108 KB	Output is correct
50	Correct	184 ms	16108 KB	Output is correct
51	Correct	163 ms	16108 KB	Output is correct
52	Correct	170 ms	16108 KB	Output is correct
53	Correct	193 ms	16108 KB	Output is correct
54	Correct	88 ms	16108 KB	Output is correct
55	Correct	85 ms	16108 KB	Output is correct
56	Correct	90 ms	16108 KB	Output is correct
57	Correct	90 ms	16256 KB	Output is correct
58	Correct	93 ms	16108 KB	Output is correct
59	Execution timed out	2088 ms	16108 KB	Time limit exceeded
60	Halted	0 ms	0 KB	-

답안 #376285

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