Submission #985068

#	Time	Username	Problem	Language	Result	Execution time	Memory
985068		siewjh	Boat (APIO16_boat)	C++17	100 / 100	484 ms	4556 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll pref[505][1005], ia[505];
ll pwr(ll a, ll b){
	ll ans = 1;
	while (b){
		if (b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
ll inv(ll a){
	return pwr(a, mod - 2);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nums; cin >> nums;
	for (int i = 1; i <= nums; i++) ia[i] = inv(i);
	vector<ll> av(nums + 1), bv(nums + 1), disc; disc.push_back(-1);
	for (int i = 1; i <= nums; i++){
		ll a, b; cin >> a >> b; b++;
		av[i] = a; bv[i] = b;
		disc.push_back(a); disc.push_back(b);
	}
	sort(disc.begin(), disc.end());
	disc.resize(distance(disc.begin(), unique(disc.begin(), disc.end())));
	int segs = disc.size() - 2;
	for (int j = 0; j <= segs; j++) pref[0][j] = 1;
	ll ans = 0;
	for (int i = 1; i <= nums; i++)
		for (int j = 1; j <= segs; j++){
			ll dpv = 0, len = disc[j + 1] - disc[j];
			if (av[i] <= disc[j] && bv[i] >= disc[j + 1]){
				ll cv = len; int cnt = 1;
				for (int k = i - 1; k >= 0; k--){
					dpv = (dpv + pref[k][j - 1] * cv % mod) % mod;
					if (av[k] <= disc[j] && bv[k] >= disc[j + 1]){
						cnt++; cv = cv * (len + cnt - 1) % mod * ia[cnt] % mod;
					}
				}
			}
			pref[i][j] = (pref[i][j - 1] + dpv) % mod;
			ans = (ans + dpv) % mod;
		}
	cout << ans;
}

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