Submission #376079

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
376079	2021-03-10T20:30:33 Z	shivensinha4	Boat (APIO16_boat)	C++17	36 / 100	1495 ms	24812 KB

boat

#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[2*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();
	memset(choose, 0, sizeof(choose)); memset(dp, 0, sizeof(dp));
	
	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) * modInverse(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]) % mod;
			}
		}
		c = 1-c;
	}
	
	cout << (dp[1-c][0][0][0]-1+mod) % mod << endl;
	
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1375 ms	12208 KB	Output is correct
2	Correct	1381 ms	12208 KB	Output is correct
3	Correct	1402 ms	12208 KB	Output is correct
4	Correct	1411 ms	12208 KB	Output is correct
5	Correct	1416 ms	12268 KB	Output is correct
6	Correct	1364 ms	12208 KB	Output is correct
7	Correct	1457 ms	12208 KB	Output is correct
8	Correct	1455 ms	12208 KB	Output is correct
9	Correct	1462 ms	12208 KB	Output is correct
10	Correct	1459 ms	12208 KB	Output is correct
11	Correct	1455 ms	12208 KB	Output is correct
12	Correct	1495 ms	12144 KB	Output is correct
13	Correct	1341 ms	12208 KB	Output is correct
14	Correct	1357 ms	12396 KB	Output is correct
15	Correct	1494 ms	12140 KB	Output is correct
16	Correct	263 ms	12140 KB	Output is correct
17	Correct	273 ms	12268 KB	Output is correct
18	Correct	272 ms	12140 KB	Output is correct
19	Correct	281 ms	12196 KB	Output is correct
20	Correct	263 ms	12268 KB	Output is correct

Subtask #2
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1375 ms	12208 KB	Output is correct
2	Correct	1381 ms	12208 KB	Output is correct
3	Correct	1402 ms	12208 KB	Output is correct
4	Correct	1411 ms	12208 KB	Output is correct
5	Correct	1416 ms	12268 KB	Output is correct
6	Correct	1364 ms	12208 KB	Output is correct
7	Correct	1457 ms	12208 KB	Output is correct
8	Correct	1455 ms	12208 KB	Output is correct
9	Correct	1462 ms	12208 KB	Output is correct
10	Correct	1459 ms	12208 KB	Output is correct
11	Correct	1455 ms	12208 KB	Output is correct
12	Correct	1495 ms	12144 KB	Output is correct
13	Correct	1341 ms	12208 KB	Output is correct
14	Correct	1357 ms	12396 KB	Output is correct
15	Correct	1494 ms	12140 KB	Output is correct
16	Correct	263 ms	12140 KB	Output is correct
17	Correct	273 ms	12268 KB	Output is correct
18	Correct	272 ms	12140 KB	Output is correct
19	Correct	281 ms	12196 KB	Output is correct
20	Correct	263 ms	12268 KB	Output is correct
21	Runtime error	25 ms	24812 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	169 ms	12140 KB	Output is correct
2	Correct	172 ms	12140 KB	Output is correct
3	Correct	172 ms	12188 KB	Output is correct
4	Correct	200 ms	12268 KB	Output is correct
5	Correct	220 ms	12140 KB	Output is correct
6	Correct	175 ms	12140 KB	Output is correct
7	Correct	171 ms	12140 KB	Output is correct
8	Correct	183 ms	12268 KB	Output is correct
9	Correct	172 ms	12140 KB	Output is correct
10	Correct	165 ms	12140 KB	Output is correct
11	Correct	171 ms	12268 KB	Output is correct
12	Correct	187 ms	12268 KB	Output is correct
13	Correct	167 ms	12268 KB	Output is correct
14	Correct	192 ms	12268 KB	Output is correct
15	Correct	170 ms	12268 KB	Output is correct
16	Correct	82 ms	12140 KB	Output is correct
17	Correct	86 ms	12184 KB	Output is correct
18	Correct	79 ms	12140 KB	Output is correct
19	Correct	95 ms	12140 KB	Output is correct
20	Correct	83 ms	12140 KB	Output is correct

Subtask #4
0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1375 ms	12208 KB	Output is correct
2	Correct	1381 ms	12208 KB	Output is correct
3	Correct	1402 ms	12208 KB	Output is correct
4	Correct	1411 ms	12208 KB	Output is correct
5	Correct	1416 ms	12268 KB	Output is correct
6	Correct	1364 ms	12208 KB	Output is correct
7	Correct	1457 ms	12208 KB	Output is correct
8	Correct	1455 ms	12208 KB	Output is correct
9	Correct	1462 ms	12208 KB	Output is correct
10	Correct	1459 ms	12208 KB	Output is correct
11	Correct	1455 ms	12208 KB	Output is correct
12	Correct	1495 ms	12144 KB	Output is correct
13	Correct	1341 ms	12208 KB	Output is correct
14	Correct	1357 ms	12396 KB	Output is correct
15	Correct	1494 ms	12140 KB	Output is correct
16	Correct	263 ms	12140 KB	Output is correct
17	Correct	273 ms	12268 KB	Output is correct
18	Correct	272 ms	12140 KB	Output is correct
19	Correct	281 ms	12196 KB	Output is correct
20	Correct	263 ms	12268 KB	Output is correct
21	Runtime error	25 ms	24812 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-

Submission #376079

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