oj.uz

Submission #376065

# Submission time Handle Problem Language Result Execution time Memory
376065 2021-03-10T20:20:36 Z shivensinha4 Boat (APIO16_boat) C++17
27 / 100
 1447 ms 16876 KB 
#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);
}


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;
	}
	
	// for (auto &i: seg) cout << i[0] << " " << i[1] << endl;
	
	int ns = seg.size();
	ll choose[ns][ns+1], dp[2][n+1][n+1][2];
	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, seg[s][1]-seg[s][0]+1); ct >= 0; ct--) {
			dp[c][ct][n][0] = choose[s][ct];
			// cout << "base case " << s << " " << ct << " " << n << " -> " << dp[c][ct][n] << endl;
			if (ct == n) continue;
			
			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;
				// cout << "segment: " << s << " with already taken: " << ct << " and currently at idx: " << idx << " -> " << dp[c][ct][idx] << endl;
				
				dp[c][ct][idx][0] = (dp[c][ct][idx][1] + dp[c][ct][idx+1][0]) % mod;
			}
		}
		c = 1-c;
	}
	
	cout << (dp[0][0][0][0]-1+mod) % mod << endl;
	
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1432 ms 16104 KB Output is correct
2 Correct 1430 ms 16108 KB Output is correct
3 Correct 1447 ms 16104 KB Output is correct
4 Correct 1438 ms 16108 KB Output is correct
5 Correct 1442 ms 16108 KB Output is correct
6 Correct 1400 ms 15980 KB Output is correct
7 Correct 1383 ms 16108 KB Output is correct
8 Correct 1377 ms 16108 KB Output is correct
9 Correct 1367 ms 16108 KB Output is correct
10 Correct 1397 ms 16108 KB Output is correct
11 Correct 1406 ms 16104 KB Output is correct
12 Correct 1381 ms 15980 KB Output is correct
13 Correct 1385 ms 16108 KB Output is correct
14 Correct 1424 ms 16108 KB Output is correct
15 Correct 1396 ms 16104 KB Output is correct
16 Runtime error 35 ms 16876 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1432 ms 16104 KB Output is correct
2 Correct 1430 ms 16108 KB Output is correct
3 Correct 1447 ms 16104 KB Output is correct
4 Correct 1438 ms 16108 KB Output is correct
5 Correct 1442 ms 16108 KB Output is correct
6 Correct 1400 ms 15980 KB Output is correct
7 Correct 1383 ms 16108 KB Output is correct
8 Correct 1377 ms 16108 KB Output is correct
9 Correct 1367 ms 16108 KB Output is correct
10 Correct 1397 ms 16108 KB Output is correct
11 Correct 1406 ms 16104 KB Output is correct
12 Correct 1381 ms 15980 KB Output is correct
13 Correct 1385 ms 16108 KB Output is correct
14 Correct 1424 ms 16108 KB Output is correct
15 Correct 1396 ms 16104 KB Output is correct
16 Runtime error 35 ms 16876 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1900 KB Output is correct
2 Correct 29 ms 1900 KB Output is correct
3 Correct 32 ms 1900 KB Output is correct
4 Correct 30 ms 1900 KB Output is correct
5 Correct 31 ms 1944 KB Output is correct
6 Correct 32 ms 1900 KB Output is correct
7 Correct 32 ms 1900 KB Output is correct
8 Correct 31 ms 1900 KB Output is correct
9 Correct 32 ms 1900 KB Output is correct
10 Correct 35 ms 1900 KB Output is correct
11 Correct 31 ms 1900 KB Output is correct
12 Correct 35 ms 1900 KB Output is correct
13 Correct 30 ms 1900 KB Output is correct
14 Correct 30 ms 1900 KB Output is correct
15 Correct 31 ms 1900 KB Output is correct
16 Correct 14 ms 876 KB Output is correct
17 Correct 13 ms 876 KB Output is correct
18 Correct 14 ms 876 KB Output is correct
19 Correct 13 ms 876 KB Output is correct
20 Correct 14 ms 876 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1432 ms 16104 KB Output is correct
2 Correct 1430 ms 16108 KB Output is correct
3 Correct 1447 ms 16104 KB Output is correct
4 Correct 1438 ms 16108 KB Output is correct
5 Correct 1442 ms 16108 KB Output is correct
6 Correct 1400 ms 15980 KB Output is correct
7 Correct 1383 ms 16108 KB Output is correct
8 Correct 1377 ms 16108 KB Output is correct
9 Correct 1367 ms 16108 KB Output is correct
10 Correct 1397 ms 16108 KB Output is correct
11 Correct 1406 ms 16104 KB Output is correct
12 Correct 1381 ms 15980 KB Output is correct
13 Correct 1385 ms 16108 KB Output is correct
14 Correct 1424 ms 16108 KB Output is correct
15 Correct 1396 ms 16104 KB Output is correct
16 Runtime error 35 ms 16876 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -