Submission #388962

#	Time	Username	Problem	Language	Result	Execution time	Memory
388962		prvocislo	Boat (APIO16_boat)	C++17	100 / 100	1050 ms	8388 KiB

boat

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
typedef long long ll;
using namespace std;

const ll mod = 1e9 + 7;
void upd(ll& a, const ll& b) { a = (a + b) % mod; }
ll mul(const ll& a, const ll& b)
{
	return (a * b) % mod;
}
ll pwr(const ll& a, const ll& b)
{
	if (!b) return 1;
	ll h = pwr(a, b >> 1);
	h = mul(h, h);
	if (b & 1) h = mul(h, a);
	return h;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n + 1), b(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
	set<int>s(a.begin(), a.end());
	for (int i = 0; i <= n; i++) s.insert(b[i] + 1);
	vector<int> v(s.begin(), s.end());
	vector<vector<ll>> c(v.size(), vector<ll>(n + 1, 0));
	for (int i = 0; i < v.size() - 1; i++)
	{
		int len = v[i + 1] - v[i];
		c[i][0] = 1;
		for (int j = 1; j <= min(n, len); j++)
			c[i][j] = mul(c[i][j - 1], mul(len - j + 1, pwr(j, mod - 2)));
	}
	vector<vector<ll> > dp(v.size(), vector<ll>(n + 1, 0));
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		ll sum = 0;
		for (int s = 0; s < v.size() - 1; s++)
		{
			ll sum2 = 0;
			// ukoncime tuto uroven
			for (int pick = 0; pick < i; pick++) upd(sum2, mul(dp[s][pick], c[s][pick]));
			if (a[i] <= v[s] && v[s] <= b[i])
			{
				for (int pick = i - 1; pick > 0; pick--)
					upd(dp[s][pick + 1], dp[s][pick]);
				upd(dp[s][1], sum);
			}
			upd(sum, sum2);
		}
		/*for (int s = 0; s < v.size() - 1; s++)
		{
			cout << v[s] << ": ";
			for (int p = 0; p <= i; p++) cout << dp[s][p] << " ";
			cout << "\n";
		}
		cout << "\n";*/
	}
	ll ans = 0;
	for (int i = 0; i < v.size(); i++)
		for (int j = 1; j <= n; j++) 
			upd(ans, mul(dp[i][j], c[i][j]));
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < v.size() - 1; i++)
      |                  ~~^~~~~~~~~~~~~~
boat.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for (int s = 0; s < v.size() - 1; s++)
      |                   ~~^~~~~~~~~~~~~~
boat.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~

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