Submission #544797

#	Time	Username	Problem	Language	Result	Execution time	Memory
544797		valerikk	Boat (APIO16_boat)	C++17	100 / 100	653 ms	7388 KiB

boat

#include <bits/stdc++.h>

using namespace std;

const int M = 1e9 + 7;

int add(int a, int b) {
	return a + b < M ? a + b : a + b - M;
}

int sub(int a, int b) {
	return a - b >= 0 ? a - b : a - b + M;
}

int mul(int a, int b) {
	return a * 1ll * b % M;
}

int pw(int a, int n) {
	int res = 1;
	for (; n > 0; n >>= 1, a = mul(a, a)) {
		if (n & 1) {
			res = mul(res, a);
		}
	}
	return res;
}

int inv(int a) {
	return pw(a, M - 2);
}

const int N = 505;

int n;
int a[N], b[N];
int m;
int x[2 * N];
int len[2 * N];
int bigc[2 * N][N];
int c[N][N];
int sumc[2 * N][N];
int dp[2 * N][N];
int pref[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		++b[i];
	}

	for (int i = 0; i < n; ++i) {
		x[2 * i] = a[i];
		x[2 * i + 1] = b[i];
	}
	sort(x, x + 2 * n);
	m = unique(x, x + 2 * n) - x - 1;

	for (int i = 0; i < m; ++i) {
		len[i] = x[i + 1] - x[i];
		bigc[i][0] = 1;
		for (int j = 1; j <= min(len[i], n); ++j) {
			bigc[i][j] = mul(bigc[i][j - 1], mul(len[i] - j + 1, inv(j)));
		}
	}

	c[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		c[i][0] = c[i][i] = 1;
		for (int j = 1; j < i; ++j) {
			c[i][j] = add(c[i - 1][j - 1], c[i - 1][j]);
		}
	}

	for (int i = 0; i < m; ++i) {
		for (int j = 1; j <= n; ++j) {
			for (int k = 1; k <= min(len[i], j); ++k) {
				sumc[i][j] = add(sumc[i][j], mul(bigc[i][k], c[j - 1][k - 1]));
			}
		}
	}

	for (int j = 0; j < m; ++j) {
		for (int i = 0; i < n; ++i) {
			pref[i + 1] = pref[i] + (x[j] >= a[i] && x[j + 1] <= b[i]);
		}
		for (int i = 0; i < n; ++i) {
			if (x[j] >= a[i] && x[j + 1] <= b[i]) {
				dp[j][i] = sumc[j][pref[i + 1]];
			}
		}
		if (j > 0) {
			for (int i = 0; i < n; ++i) {
				if (x[j] >= a[i] && x[j + 1] <= b[i]) {
					for (int k = 0; k < i; ++k) {
						dp[j][i] = add(dp[j][i], mul(dp[j - 1][k], sumc[j][pref[i + 1] - pref[k + 1]]));
					}
				}
			}
			for (int i = 0; i < n; ++i) {
				dp[j][i] = add(dp[j][i], dp[j - 1][i]);
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < n; ++i) {
		ans = add(ans, dp[m - 1][i]);
	}
	cout << ans << endl;

	return 0;
}

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