oj.uz

Submission #969342

# Submission time Handle Problem Language Result Execution time Memory
969342 2024-04-25T02:57:19 Z MinaRagy06 Boat (APIO16_boat) C++17
9 / 100
 491 ms 6492 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()

const int mod = 1e9 + 7;
struct mint {
	int v;
	mint(long long x) {
		if (x >= mod) x %= mod;
		v = x;
	}
	mint() {v = 0;}
	mint& operator+=(mint b) {
		if ((v += b.v) >= mod) {
			v -= mod;
		}
		return *this;
	}
	mint& operator-=(mint b) {
		if ((v -= b.v) < 0) {
			v += mod;
		}
		return *this;
	}
	mint& operator*=(mint b) {
		v = 1ll * v * b.v % mod;
		return *this;
	}
	mint power(mint a, int b) {
		mint ans = 1;
		while (b) {
			if (b & 1) {
				ans *= a;
			}
			a *= a, b >>= 1;
		}
		return ans;
	}
	mint& operator/=(mint b) {
		v = 1ll * v * power(b, mod - 2).v % mod;
		return *this;
	}
	friend mint operator+(mint a, mint b) {
		return a += b;
	}
	friend mint operator-(mint a, mint b) {
		return a -= b;
	}
	friend mint operator*(mint a, mint b) {
		return a *= b;
	}
	friend mint operator/(mint a, mint b) {
		return a /= b;
	}
	friend istream& operator>>(istream &is, mint &a) {
		return is >> a.v;
	}
	friend ostream& operator<<(ostream &os, mint a) {
		return os << a.v;
	}
};
const int N = 505;
mint fact[N], inv[N];
mint nCr(int n, int r) {
	if (n < 0 || r < 0 || n - r < 0) return 0;
//	cout << "> " << n << ' ' << r << ' ' << fact[n] * inv[r] * inv[n - r] << '\n';
	return fact[n] * inv[r] * inv[n - r];
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	fact[0] = 1;
	for (int i = 1; i < N; i++) {
		fact[i] = fact[i - 1] * i;
	}
	inv[N - 1] = 1 / fact[N - 1];
	for (int i = N - 2; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1);
	}
	int n;
	cin >> n;
	array<int, 2> a[n];
	vector<int> v;
	for (int i = 0; i < n; i++) {
		cin >> a[i][0] >> a[i][1];
		v.push_back(a[i][0]);
		v.push_back(a[i][1]);
		v.push_back(a[i][1] + 1);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	auto get = [&] (int x) {
		return lower_bound(v.begin(), v.end(), x) - v.begin();
	};
	int m = v.size();
	vector<int> gud[m];
	for (int i = 0; i < n; i++) {
		int l = get(a[i][0]), r = get(a[i][1]);
		for (int j = l; j <= r; j++) {
			gud[j].push_back(i + 1);
		}
	}
	mint dp[m + 1][n + 1];
	for (int j = 1; j <= n; j++) {
		dp[m][j] = 1;
	}
	for (int i = m - 1; i >= 0; i--) {
		int sz = gud[i].size();
		mint dp2[sz + 1][sz + 1];
		for (int j = sz - 1; j >= 0; j--) {
			for (int k = 1; k <= sz; k++) {
				dp2[j][k] += dp2[j + 1][k];
				if (k == 1) {
					dp2[j][k] += dp[i + 1][gud[i][j]];
				} else {
					dp2[j][k] += dp2[j + 1][k - 1];
				}
			}
		}
		for (int j = 0; j <= n; j++) {
			int pos = SZ(gud[i]);
			for (int k = 0; k < SZ(gud[i]); k++) {
				if (j < gud[i][k]) {
					pos = k;
					break;
				}
			}
			dp[i][j] = dp[i + 1][j];
			for (int k = 1; k <= SZ(gud[i]) - pos; k++) {
//				cout << k << ' ' << dp2[pos][k] << ' ' << v[i + 1] - v[i] << ' ' << k << ' ' << nCr(v[i + 1] - v[i], k) << '\n';
				dp[i][j] += dp2[pos][k] * nCr(v[i + 1] - v[i], k);
			}
		}
	}
//	for (int i = 0; i < m; i++) {
//		for (int j = 0; j <= n; j++) {
//			cout << dp[i][j] << ' ';
//		}
//		cout << '\n';
//	}
	cout << dp[0][0] << '\n';
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2464 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2468 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 3 ms 2392 KB Output is correct
8 Correct 4 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 5 ms 2396 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 4 ms 2396 KB Output is correct
14 Correct 3 ms 2396 KB Output is correct
15 Correct 3 ms 2392 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 2 ms 860 KB Output is correct
20 Correct 2 ms 604 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2464 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2468 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 3 ms 2392 KB Output is correct
8 Correct 4 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 5 ms 2396 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 4 ms 2396 KB Output is correct
14 Correct 3 ms 2396 KB Output is correct
15 Correct 3 ms 2392 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 2 ms 860 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 285 ms 4628 KB Output is correct
22 Correct 270 ms 4524 KB Output is correct
23 Correct 246 ms 4240 KB Output is correct
24 Correct 271 ms 4448 KB Output is correct
25 Correct 292 ms 4524 KB Output is correct
26 Correct 443 ms 5480 KB Output is correct
27 Correct 491 ms 5464 KB Output is correct
28 Correct 489 ms 5568 KB Output is correct
29 Correct 453 ms 5460 KB Output is correct
30 Runtime error 5 ms 6492 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct
3 Correct 3 ms 2464 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 3 ms 2468 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 3 ms 2392 KB Output is correct
8 Correct 4 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 5 ms 2396 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 4 ms 2396 KB Output is correct
14 Correct 3 ms 2396 KB Output is correct
15 Correct 3 ms 2392 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 2 ms 860 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 285 ms 4628 KB Output is correct
22 Correct 270 ms 4524 KB Output is correct
23 Correct 246 ms 4240 KB Output is correct
24 Correct 271 ms 4448 KB Output is correct
25 Correct 292 ms 4524 KB Output is correct
26 Correct 443 ms 5480 KB Output is correct
27 Correct 491 ms 5464 KB Output is correct
28 Correct 489 ms 5568 KB Output is correct
29 Correct 453 ms 5460 KB Output is correct
30 Runtime error 5 ms 6492 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -