Submission #1293443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293443		kian2009	Boat (APIO16_boat)	C++20	100 / 100	1465 ms	8592 KiB

boat

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 5e2 + 10, MAXM = 1e3 + 10, mod = 1e9 + 7;

ll n, a[MAXN], b[MAXN], fact[MAXN], inv[MAXN], I[MAXN];
ll dp[MAXM][MAXN], f[MAXN][MAXN], ps[MAXN][MAXN];
vector<int> num;

ll findMod(ll a, ll b) {
	if (b == 0)
		return 1;
	ll t = findMod(a, b / 2);
	if (b % 2 == 0)
		return (t * t) % mod;
	return (((t * t) % mod) * a) % mod;	
}

ll find(ll a, ll b) {
	return (a * findMod(b, mod - 2)) % mod;	
}

void calcFact() {
	fact[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		fact[i] = (fact[i - 1] * i) % mod;
		I[i] = find(1, i);	
	}	
	inv[MAXN - 1] = find(1, fact[MAXN - 1]) % mod;
	for (int i = MAXN - 2; i >= 0; i--)
		inv[i] = (inv[i + 1] * (i + 1)) % mod;
}

ll crn(ll a, ll b) {
	if (b < 0 || (a < 0 || a > b))
		return 0;
	return (fact[b] * ((inv[a] * inv[b - a]) % mod)) % mod;	
}

void input() {
	cin >> n;
	num.push_back(1);
	num.push_back(1e9 + 1);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
		num.push_back(a[i]);
		num.push_back(b[i] + 1);
	}
	sort(num.begin(), num.end());
	num.resize(unique(num.begin(), num.end()) - num.begin());
}

bool check(int i, int j) {
	return (a[i] <= num[j] && b[i] >= (num[j + 1] - 1));	
}

void calcDp() {
	for (int j = 0; j < num.size() - 1; j++) {
		ll l = num[j + 1] - num[j];
		for (int x = 1; x <= n; x++) {
			ll comb = 1;
			for (int i = 1; i <= x; i++) {
				comb = (((comb * (l - i + 1)) % mod) * I[i]) % mod;
				f[x][i] = (comb * crn(i - 1, x - 1)) % mod;
				ps[x][i] = (ps[x][i - 1] + f[x][i]) % mod;
			}
		}
		for (int i = 0; i < n; i++) {
			int cnt = 0;
			dp[j][i] = (!j? 1: dp[j - 1][i]);
			for (int k = i; k >= 0; k--) {
				if (check(k, j)) {
					cnt++;
					dp[j][i] = (dp[j][i] + ps[cnt][cnt] * ((k == 0 || j == 0)? 1: dp[j - 1][k - 1])) % mod;
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	calcFact();
	input();
	calcDp();
	cout << (dp[num.size() - 2][n - 1] - 1 + mod) % mod << endl;
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42