Submission #252196

#	Time	Username	Problem	Language	Result	Execution time	Memory
252196		Berted	Boat (APIO16_boat)	C++14	100 / 100	1273 ms	24056 KiB

boat

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

const ll MD = 1e9 + 7;

ll dp[501][2002], pf[501][2002], pre[2002][501];
int n, a[501], b[501], c[2002], sz = 1;

inline ll pw(ll b, ll e)
{
	e = (e + MD - 1) % (MD - 1);
	ll t = 1;
	while (e)
	{
		if (e & 1) {t = (t * b) % MD;}
		b = (b * b) % MD; e >>= 1;
	}
	return t;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i] >> b[i];
		c[sz++] = a[i];
		c[sz++] = a[i] - 1;
		c[sz++] = b[i] + 1;
		c[sz++] = b[i];
	}
	sort(c, c + sz);
	sz = unique(c, c + sz) - c;

	for (int i = 1; i < sz; i++)
	{
		ll cur = 1;
		for (int j = 0; j <= n; j++)
		{
			pre[i][j] = cur;
			cur = (cur * (c[i] - c[i - 1] + j)) % MD;
			cur = (cur * pw(j + 1, -1)) % MD;
		}
	}

	dp[0][0] = 1;
	pf[0][0] = 1;
	for (int j = 1; j < sz; j++) {pf[0][j] = pf[0][j - 1];}
	for (int i = 1; i <= n; i++)
	{
		pf[i][0] = dp[i][0] = 1;
		for (int j = 1; j < sz; j++)
		{
			int kk = 0;
			for (int k = i - 1; k >= 0; k--)
			{
				kk += (a[k] <= c[j - 1] + 1) && (c[j] <= b[k]);
				if (kk && ((a[k] <= c[j - 1] + 1) && (c[j] <= b[k])))
				{
					dp[i][j] = (dp[i][j] + pf[k][j - 1] * pre[j][kk] % MD) % MD;
				}
			}
			// cout << "DP " << i << " " << j << " " << dp[i][j] << "\n";
			pf[i][j] = (pf[i][j - 1] + dp[i][j]) % MD;
		}
	}
	ll res = 0;
	for (int j = 1; j < sz; j++) res = (res + dp[n][j]) % MD;
	cout << res << "\n";
	return 0;
}

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