Submission #101889

#	Time	Username	Problem	Language	Result	Execution time	Memory
101889		KCSC	Boat (APIO16_boat)	C++14	100 / 100	671 ms	3456 KiB

boat

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

const int DIM = 505;
const int MOD = 1000000007;

vector<int> lst;
pair<int, int> seg[DIM];

int dp[DIM], dp2[DIM][DIM];
int fct[DIM], inv[DIM], cmb[DIM * 2][DIM];

int logPow(int x, int n) {
	if (!n) { return 1; }
	int y = logPow(x, n >> 1);
	if (n | 1) { y = 1LL * y * y % MOD; }
	if (n & 1) { y = 1LL * y * x % MOD; }
	return y; }

int main(void) {
#ifdef HOME
	freopen("boat.in", "r", stdin);
	freopen("boat.out", "w", stdout);
#endif
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> seg[i].first >> seg[i].second;
		lst.push_back(seg[i].first); lst.push_back(++seg[i].second); }
	sort(lst.begin(), lst.end());
	lst.resize(unique(lst.begin(), lst.end()) - lst.begin());
	fct[0] = inv[0] = 1;
	for (int i = 1; i <= n; ++i) {
		fct[i] = 1LL * fct[i - 1] * i % MOD;
		inv[i] = logPow(fct[i], MOD - 2); }
	for (int i = 1; i < lst.size(); ++i) {
		int dif = lst[i] - lst[i - 1];
		cmb[i][0] = 1;
		for (int j = 1; j <= n; ++j) {
			cmb[i][j] = 1LL * cmb[i][j - 1] * (dif - j + 1) % MOD; }
		for (int j = 1; j <= n; ++j) {
			cmb[i][j] = 1LL * cmb[i][j] * inv[j] % MOD; } }
	for (int i = 0; i <= n; ++i) {
		dp[i] = 1; }
	for (int i = 1; i < lst.size(); ++i) {
		int dif = lst[i] - lst[i - 1];
		for (int j = 0; j <= n; ++j) {
			dp2[0][j] = dp[j]; }
		for (int j = 1; j <= min(dif, n); ++j) {
			for (int k = j; k <= n; ++k) {
				dp2[j][k] = dp2[j][k - 1];
				if (seg[k].first <= lst[i - 1] and seg[k].second >= lst[i]) {
					dp2[j][k] = (dp2[j][k] + dp2[j - 1][k - 1]) % MOD; }
				dp[k] = (1LL * dp2[j][k] * cmb[i][j] + dp[k]) % MOD; } } }
	cout << (dp[n] - 1 + MOD) % MOD;
	return 0; }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < lst.size(); ++i) {
                  ~~^~~~~~~~~~~~
boat.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < lst.size(); ++i) {
                  ~~^~~~~~~~~~~~

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