Submission #1209865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209865		k1r1t0	Boat (APIO16_boat)	C++20	100 / 100	509 ms	8600 KiB

boat

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 1100;
const int MOD = (int)(1e9+7);

int n, m, a[N], b[N], dp[N][N], vv[N];
vector<int> pos;

void init() {
	for (int i = 1; i < N; i++)
		vv[i] = (i == 1 ? 1 : MOD - MOD / i * vv[MOD % i] % MOD);
}

int sz(int k) {
	return pos[k] - pos[k - 1];
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	init();
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		pos.push_back(a[i]);
		pos.push_back(b[i] + 1);
	}
	sort(begin(pos), end(pos));
	pos.erase(unique(begin(pos), end(pos)), end(pos));
	m = (int) pos.size() - 1;
	for (int i = 1; i <= n; i++) {
		int sum = 1;
		for (int j = 1; j <= m; j++) {
			int old = 0;
			for (int k = 1; k <= n; k++)
				old += dp[j][k];
			if (a[i] <= pos[j - 1] && pos[j] <= b[i] + 1) {
				for (int k = n; k >= 1; k--)
					if (k == 1)
						(dp[j][k] += sum * sz(j)) %= MOD;
					else
						(dp[j][k] += dp[j][k - 1] * (sz(j) - k + 1) % MOD * vv[k]) %= MOD;
			}
			(sum += old) %= MOD;
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; i++)
	for (int j = 1; j <= n; j++)
		(ans += dp[i][j]) %= MOD;
	cout << ans;
}

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