Submission #954820

#	Time	Username	Problem	Language	Result	Execution time	Memory
954820		Itamar	Boat (APIO16_boat)	C++14	100 / 100	915 ms	2860 KiB

boat

#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define x first
#define y second
#define pd pair<double,double>

const int siz = 502;
ll a[siz], b[siz];

ll ch[siz][siz];
ll invfac[siz];
ll inv[siz];
const int mod = 1e9 + 7;

ll powi(ll a, ll b) {
	if (b == 0)return 1;
	ll ans = powi(a, b / 2);
	ans = (ans * ans) % mod;
	if (b % 2)ans = (ans * a) % mod;
	return ans;
}
int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i] >> b[i];

	vll v; for (int i = 0; i < n; i++) { v.push_back(a[i]); v.push_back(b[i]); v.push_back(b[i] + 1); }
	sort(v.begin(), v.end());

	for (int i = 0; i < siz; i++)inv[i] = powi(i, mod - 2);
	invfac[0] = 1;
	for (int i = 1; i < siz; i++)invfac[i] = (inv[i] * invfac[i - 1])%mod;

	for (int i = 0; i < siz; i++) {
		for (int j = 0; j <= i; j++) {
			ch[i][j] = (invfac[j] * invfac[i - j]) % mod;
			ch[i][j] = (ch[i][j] * powi(invfac[i], mod - 2)) % mod;
		}
	}

	vll dp(n);
	for (int i = 0; i < v.size()-1; i++) {
		ll N = v[i+1]-v[i];
		if (N <= 0)continue;
		vll nc(siz);
		nc[0] = 1;
		for (int j = 1; j < siz; j++) {
			nc[j] = ((N - j + 1) * nc[j - 1]) % mod;
			nc[j] = (nc[j] * inv[j]) % mod;
		}
		vll form(siz);
		for (int j = 0; j+2 < siz; j++) {
			for (int f = 0; f <= j; f++) {
				form[j] += nc[f + 2] * ch[j][f];
				form[j] %= mod;
			}
		}
		vll dpt=dp;
		ll sum = 0;
		for (int j = 0; j < n; j++) {
			if (a[j] <= v[i] && b[j] >= v[i + 1] - 1) {
				int bet = 0;
				dpt[j] += (sum + 1) * N;
				dpt[j] %= mod;
				for (int f = j + 1; f < n; f++) {
					if (a[f] <= v[i] && b[f] >= v[i + 1] - 1) {
						dpt[f] += (sum + 1) * form[bet];
						dpt[f] %= mod;
						bet++;
					}
				}
			}
			sum += dp[j];
			sum %= mod;
		}
		dp = dpt;
	}
	ll ans = 0; for (int i = 0; i < n; i++)ans += dp[i];
	ans %= mod;
	cout << ans;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Compilation message (stderr)

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

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