Submission #47504

#	Time	Username	Problem	Language	Result	Execution time	Memory
47504		jun6873	Boat (APIO16_boat)	C++11	100 / 100	1548 ms	5616 KiB

boat

#include <bits/stdc++.h>
using namespace std;

int n, a[504], b[504], cn, mi[504], c[1004], num[1004], m[1004][504], s0[1004], s[1004][504];

const int mod = 1000000007;
int sum(int x, int y) { return (x+y) % mod; }
int mul(int x, int y) { return (x*(long long)y) % mod; }
int power(int x, int k) {
	if (!k) return 1;
	if (k&1) return mul(x, power(x, k-1));
	int r = power(x, k/2); return mul(r, r);
}

int main() {
	cin >> n;
	for (int i=0; i<n; i++) cin >> a[i] >> b[i];
	for (int i=0; i<n; i++) c[2*i] = a[i], c[2*i+1] = b[i]+1;

	sort(c, c+2*n+1);
	cn = unique(c, c+2*n+1) - c;
	for (int i=0; i<n; i++) {
		a[i] = lower_bound(c, c+cn, a[i]) - c;
		b[i] = lower_bound(c, c+cn, b[i]+1) - c;
	}

	for (int i=1; i<504; i++) mi[i] = power(i, mod-2);

	s0[0] = 1;
	s[0][1] = 1; num[0] = 1;
	int ans = 0;
	for (int i=0; i<n; i++) {
		memset(m, 0, sizeof(m));
		for (int j=a[i]; j<b[i]; j++) num[j]++;
		for (int j=a[i]; j<b[i]; j++) for (int jb=0; jb<j; jb++) m[j][1] = sum(m[j][1], mul(c[j+1]-c[j], s0[jb]));
		for (int j=a[i]; j<b[i]; j++) for (int k=2; k<=num[j]; k++) m[j][k] = mul(mul(max(0, c[j+1]-c[j]-k+1), mi[k]), s[j][k-1]);

		for (int j=a[i]; j<b[i]; j++) for (int k=1; k<=num[j]; k++) ans = sum(ans, m[j][k]);
		for (int j=0; j<cn; j++) for (int k=1; k<=num[j]; k++) s0[j] = sum(s0[j], m[j][k]);
		for (int j=0; j<cn; j++) for (int k=1; k<=num[j]; k++) s[j][k] = sum(s[j][k], m[j][k]);
	}

	cout << ans;
}

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