Submission #1228489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228489		Bui_Quoc_Cuong	Boat (APIO16_boat)	C++20	100 / 100	634 ms	4428 KiB

boat

#include <bits/stdc++.h>
using namespace std;
#define int 	long long
#define MAXN  	505
#define MOD		(int)(1e9 + 7)
int n;
int a[MAXN], b[MAXN];
int dp[2 * MAXN][MAXN];
int fact[MAXN], inv_fact[MAXN];
int Pow(int x, int y) {
	if (y == 0) return 1;
	if (y == 1) return x;
	int c = Pow(x, y / 2);
	if (y & 1) return 1LL * c * c % MOD * x % MOD;
	else return 1LL * c * c % MOD;
}
void add(int &x, const int y) {
	x+= y;
	x %= MOD;
}
signed main() {
	cin.tie(nullptr) -> sync_with_stdio(false);
	// freopen("kieuoanh.inp", "r", stdin);
	// freopen("kieuoanh.out", "w", stdout);
	cin >> n;
	vector <int> seg;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		seg.push_back(a[i]);
		seg.push_back(b[i] + 1);
	}
	seg.push_back(0);
	sort(seg.begin(), seg.end());
	seg.resize(unique(seg.begin(), seg.end()) - seg.begin());
	int m = (int) seg.size();
	for (int i = 0; i <= n; i++) {
		dp[0][i] = 1;
		inv_fact[i] = Pow(i, MOD - 2);
	}
	for (int j = 1; j < m - 1; j++) {
		int x = seg[j + 1] - seg[j];
		for (int i = 0; i <= n; i++) {
			add(dp[j][i], dp[j - 1][i]);
			int nCk = 1, cnt = 0;
			for (int last = i; last >= 1; last--) {
				if (a[last] <= seg[j] && seg[j + 1] - 1 <= b[last]) {
					cnt++;
					nCk = 1LL * nCk * (x + cnt - 1) % MOD * inv_fact[cnt] % MOD;
					add(dp[j][i], 1LL * dp[j - 1][last - 1] * nCk % MOD);
				}
			}
		}
	}
	cout << (dp[m - 2][n] - 1 + MOD) % MOD;
	return 0;
}

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