oj.uz

Submission #47475

# Submission time Handle Problem Language Result Execution time Memory
47475 2018-05-03T13:44:39 Z jun6873 Boat (APIO16_boat) C++11
0 / 100
 59 ms 4344 KB 
#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] += 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 4344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 4344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 4344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 4344 KB Output isn't correct
2 Halted 0 ms 0 KB -