Submission #859921

#	Time	Username	Problem	Language	Result	Execution time	Memory
859921		bliss08	Boat (APIO16_boat)	C++17	100 / 100	480 ms	4692 KiB

boat

#include <bits/stdc++.h>
#define ll long long
#define MOD (ll)(1e9 + 7)

using namespace std;

ll lo[1020], hi[1020];

ll A[510], B[510], baser[510];

ll dp[510][1020];

ll cnt, tot, N;

void add_mod(ll& ret, ll params)
{
	ret += params;
	ret %= MOD;
}

void mul_mod(ll& ret, ll params)
{
	ret *= params;
	ret %= MOD;
}

void sub_mod(ll& ret, ll params)
{
	ret = (ret - params + MOD) % MOD;
}

void precomp()
{
	baser[1] = 1;

	for (ll i = 2; i <= N; i++)
	{
		baser[i] = MOD - (MOD / i);
		mul_mod(baser[i], baser[MOD % i]);
	}

	stable_sort(hi + 1, hi + cnt + 1);
	cnt = unique(hi + 1, hi + cnt + 1) - hi;

	for (ll i = 1; i <= N; i++)
	{
		A[i] = lower_bound(hi + 1, hi + cnt, A[i]) - hi;
		B[i] = lower_bound(hi + 1, hi + cnt, B[i]) - hi;
	}

	cnt -= 2;

	for (ll i = 1; i <= cnt; i++)
	{
		lo[i] = hi[i + 1];
		sub_mod(lo[i], hi[i]);
	}
}

void solve()
{
	for (ll i = 0; i <= cnt; i++)
		dp[0][i] = 1;

	for (ll i = 1; i <= N; i++)
	{
		for (ll j = A[i], t = B[i]; j < t; j++)
		{
			ll C = lo[j], r = lo[j], inn = 1;

			for (ll k = i - 1; k >= 0; k--)
			{
				ll tmp = dp[k][j - 1];
				mul_mod(tmp, C);
				add_mod(dp[i][j], tmp);

				if (A[k] > j || j >= B[k])
					continue;

				r++, inn++;
				tmp = C;
				mul_mod(tmp, r);
				mul_mod(tmp, baser[inn]);
				C = tmp;
			}
		}

		for (ll j = 2; j <= cnt; j++)
			add_mod(dp[i][j], dp[i][j - 1]);
	}

	for (ll i = 1; i <= N; i++)
		add_mod(tot, dp[i][cnt]);
}

int main()
{
	cin >> N;

	for (ll i = 1; i <= N; i++)
	{
		cin >> A[i] >> B[i];
		hi[++cnt] = A[i];
		hi[++cnt] = ++B[i];
	}

	precomp();

	solve();

	cout << tot;
}

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