Submission #1031407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031407		Tob	Boat (APIO16_boat)	C++14	100 / 100	1002 ms	7508 KiB

boat

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 507, mod = 1e9 + 7;

int add(int x, int y) {return (x+y < mod) ? x+y : x+y-mod;}
int mul(int x, int y) {return (ll)x*y%mod;}

int n;
int aa[N], bb[N], a[N], b[N], dp[N][2*N], ch[N][2*N], c[N][2*N], inv[N], cho[N][N];

int Pow(int x, int y) {
	int res = 1, pot = x;
	while (y) {
		if (y % 2) res = mul(res, pot);
		pot = mul(pot, pot);
		y /= 2;
	}
	return res;
}

int main () {
	FIO;
	inv[0] = 1;
	for (int i = 1; i < N; i++) inv[i] = Pow(i, mod-2);
	for (int i = 0; i < N; i++) {
		cho[i][0] = 1;
		for (int j = 1; j <= i; j++) cho[i][j] = add(cho[i-1][j], cho[i-1][j-1]);
	}
	cin >> n;
	vector <int> v;
	map <int, int> saz;
	for (int i = 0; i < n; i++) {
		cin >> aa[i] >> bb[i]; bb[i]++;
		v.pb(aa[i]);
		v.pb(bb[i]);
	}
	sort(all(v)); v.erase(unique(all(v)), v.end());
	int siz = v.size()-1;
	for (int i = 0; i <= siz; i++) saz[v[i]] = i;
	for (int i = 0; i < n; i++) {
		a[i] = saz[aa[i]];
		b[i] = saz[bb[i]];
	}
	for (int i = 0; i < siz; i++) {
		int x = v[i+1]-v[i];
		for (int j = 1; j <= min(n,x); j++) {
			int pro = 1;
			for (int k = x, l = 1; k > x-j; k--, l++) pro = mul(pro, mul(k, inv[l]));
			ch[j][i] = pro;
		}
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= min(j,x); k++) {
				c[j][i] = add(c[j][i], mul(ch[k][i], cho[j-1][k-1]));
			}
		}
	}
	for (int j = 0; j < siz; j++) {
		for (int i = 0; i < n; i++) {
			if (j) dp[i][j] = dp[i][j-1];
			if (j < a[i] || j >= b[i]) continue;
			int cnt = 1;
			for (int k = i-1; k >= 0; k--) {
				dp[i][j] = add(dp[i][j], mul(c[cnt][j], dp[k][j-1]));
				cnt += (j >= a[k] && j < b[k]);
			}
			dp[i][j] = add(dp[i][j], c[cnt][j]);
		}
	}
	
	int res = 0;
	for (int i = 0; i < n; i++) res = add(res, dp[i][siz-1]);
	
	cout << res;

	return 0;
}

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