Submission #255088

#	Time	Username	Problem	Language	Result	Execution time	Memory
255088		maximath_1	Boat (APIO16_boat)	C++11	100 / 100	448 ms	8440 KiB

boat

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;

int n;
ll st[1005], ed[1005], len[1005];
ll inv[1005], dp[1005][1005];
vector<ll> cc;

ll add(ll a, ll b){
	ll res = a + b;
	if(res >= mod) res -= mod;
	return res;
}

ll mul(ll a, ll b){
	return (a * 1ll * b) % mod;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> st[i] >> ed[i];
		ed[i] ++;
	}

	inv[1] = 1ll;
	for(int i = 2; i <= n; i ++)
		inv[i] = mul(mod / i, mod - inv[mod % i]);

	for(int i = 1; i <= n; i ++){
		cc.push_back(st[i]);cc.push_back(ed[i]);
	}
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());

	for(int i = 1; i <= n; i ++){
		st[i] = upper_bound(cc.begin(), cc.end(), st[i]) - cc.begin();
		ed[i] = upper_bound(cc.begin(), cc.end(), ed[i]) - cc.begin();
	}

	int sz = cc.size() - 1;
	for(int i = 1; i <= sz; i ++)
		len[i] = cc[i] - cc[i - 1];

	dp[0][0] = 1ll;
	for(int i = 1; i <= sz; i ++){
		dp[i][0] = 1ll;
		for(int j = 1; j <= n; j ++){
			ll choose = len[i]; int cnt = 1;
			dp[i][j] = dp[i - 1][j];
			if(i < st[j] || i >= ed[j]) continue;

			for(int k = j - 1; k >= 0; k --){
				dp[i][j] = add(dp[i][j], mul(dp[i - 1][k], choose));
				if(st[k] <= i && i < ed[k]){
					choose = mul(choose, mul(add(cnt, len[i]), inv[cnt + 1]));
					cnt ++;
				}
			}
		}
	}

	ll ans = 0ll;
	for(int i = 1; i <= n; i ++)
		ans = add(ans, dp[sz][i]);
	cout << ans << endl;
	return 0;
}

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