oj.uz

Submission #376075

# Submission time Handle Problem Language Result Execution time Memory
376075 2021-03-10T20:28:10 Z shivensinha4 Boat (APIO16_boat) C++17
36 / 100
 1485 ms 24812 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);
}

const int MXN = 500;
ll choose[2*MXN][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 1417 ms 12268 KB Output is correct
2 Correct 1443 ms 12200 KB Output is correct
3 Correct 1447 ms 12268 KB Output is correct
4 Correct 1485 ms 12268 KB Output is correct
5 Correct 1445 ms 12200 KB Output is correct
6 Correct 1373 ms 12200 KB Output is correct
7 Correct 1411 ms 12268 KB Output is correct
8 Correct 1390 ms 12288 KB Output is correct
9 Correct 1410 ms 12200 KB Output is correct
10 Correct 1400 ms 12200 KB Output is correct
11 Correct 1378 ms 12268 KB Output is correct
12 Correct 1465 ms 12140 KB Output is correct
13 Correct 1404 ms 12200 KB Output is correct
14 Correct 1387 ms 12200 KB Output is correct
15 Correct 1391 ms 12268 KB Output is correct
16 Correct 250 ms 12140 KB Output is correct
17 Correct 283 ms 12268 KB Output is correct
18 Correct 270 ms 12268 KB Output is correct
19 Correct 274 ms 12140 KB Output is correct
20 Correct 260 ms 12268 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1417 ms 12268 KB Output is correct
2 Correct 1443 ms 12200 KB Output is correct
3 Correct 1447 ms 12268 KB Output is correct
4 Correct 1485 ms 12268 KB Output is correct
5 Correct 1445 ms 12200 KB Output is correct
6 Correct 1373 ms 12200 KB Output is correct
7 Correct 1411 ms 12268 KB Output is correct
8 Correct 1390 ms 12288 KB Output is correct
9 Correct 1410 ms 12200 KB Output is correct
10 Correct 1400 ms 12200 KB Output is correct
11 Correct 1378 ms 12268 KB Output is correct
12 Correct 1465 ms 12140 KB Output is correct
13 Correct 1404 ms 12200 KB Output is correct
14 Correct 1387 ms 12200 KB Output is correct
15 Correct 1391 ms 12268 KB Output is correct
16 Correct 250 ms 12140 KB Output is correct
17 Correct 283 ms 12268 KB Output is correct
18 Correct 270 ms 12268 KB Output is correct
19 Correct 274 ms 12140 KB Output is correct
20 Correct 260 ms 12268 KB Output is correct
21 Runtime error 27 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 189 ms 12140 KB Output is correct
2 Correct 164 ms 12140 KB Output is correct
3 Correct 176 ms 12268 KB Output is correct
4 Correct 183 ms 12268 KB Output is correct
5 Correct 170 ms 12140 KB Output is correct
6 Correct 201 ms 12180 KB Output is correct
7 Correct 172 ms 12140 KB Output is correct
8 Correct 189 ms 12268 KB Output is correct
9 Correct 168 ms 12268 KB Output is correct
10 Correct 199 ms 12268 KB Output is correct
11 Correct 159 ms 12140 KB Output is correct
12 Correct 201 ms 12140 KB Output is correct
13 Correct 156 ms 12140 KB Output is correct
14 Correct 153 ms 12140 KB Output is correct
15 Correct 176 ms 12204 KB Output is correct
16 Correct 96 ms 12268 KB Output is correct
17 Correct 73 ms 12140 KB Output is correct
18 Correct 87 ms 12176 KB Output is correct
19 Correct 73 ms 12140 KB Output is correct
20 Correct 74 ms 12140 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1417 ms 12268 KB Output is correct
2 Correct 1443 ms 12200 KB Output is correct
3 Correct 1447 ms 12268 KB Output is correct
4 Correct 1485 ms 12268 KB Output is correct
5 Correct 1445 ms 12200 KB Output is correct
6 Correct 1373 ms 12200 KB Output is correct
7 Correct 1411 ms 12268 KB Output is correct
8 Correct 1390 ms 12288 KB Output is correct
9 Correct 1410 ms 12200 KB Output is correct
10 Correct 1400 ms 12200 KB Output is correct
11 Correct 1378 ms 12268 KB Output is correct
12 Correct 1465 ms 12140 KB Output is correct
13 Correct 1404 ms 12200 KB Output is correct
14 Correct 1387 ms 12200 KB Output is correct
15 Correct 1391 ms 12268 KB Output is correct
16 Correct 250 ms 12140 KB Output is correct
17 Correct 283 ms 12268 KB Output is correct
18 Correct 270 ms 12268 KB Output is correct
19 Correct 274 ms 12140 KB Output is correct
20 Correct 260 ms 12268 KB Output is correct
21 Runtime error 27 ms 24812 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -