Submission #255089

#	Time	Username	Problem	Language	Result	Execution time	Memory
255089		maximath_1	Boat (APIO16_boat)	C++11	100 / 100	469 ms	4472 KiB

boat

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

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

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

int mul(int a, int 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] = 1;
	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] = 1;
	for(int i = 1; i <= sz; i ++){
		dp[i][0] = 1;
		for(int j = 1; j <= n; j ++){
			int 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 ++;
				}
			}
		}
	}

	int ans = 0;
	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