oj.uz

Submission #45541

# Submission time Handle Problem Language Result Execution time Memory
45541 2018-04-15T09:08:58 Z fallingstar Boat (APIO16_boat) C++17
9 / 100
 741 ms 5888 KB 
/**
	Problem: Boat
	Source: APIO 2016 problem 1
*/

#include <iostream>
#include <algorithm>

#define long long long

using namespace std;

const int N = 500 + 2;
const int MOD = 1e9 + 7;

int Mul(int a, int b) { return (long) a * b % MOD; }
void Add(int &a, int b) { a += b; if (a >= MOD) a -= MOD; }
int Sum(int a, int b) { Add(a, b); return a; }
void Sub(int &a, int b) { a -= b; if (a < 0) a += MOD; }
int Pow(int x, int n)
{
	if (n == 1) return x;
	int t = Pow(x, n / 2); t = Mul(t, t);
	return n & 1 ? Mul(t, x) : t;
}

int n, a[N], b[N];
int m, p[N * 2];										// left and right ends of ranges
int c[N][N];											// c[i][j] = choose j from i
int g[N * 2][N];
int ft[N], inv[N];
int f[N][N * 2];

void Prep()												// precalculate all g(i, j)
{
	ft[0] = 1;											// calculate factorials and inverses
	for (int i = 1; i <= n; ++i) ft[i] = Mul(ft[i - 1], i);
	inv[n] = Pow(ft[n], MOD - 2);
	for (int i = n - 1; i >= 0; --i)
		inv[i] = Mul(inv[i + 1], i + 1);

	c[0][0] = 1;
	for (int i = 1; i <= n; ++i)						// calculate all c(i, j) with i, j <= n					
	{
		c[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			c[i][j] = Sum(c[i - 1][j], c[i - 1][j - 1]);
	}
	
	for (int i = 1; i < m; ++i)
	{
		int tmp[N] = {}, len = p[i] - p[i - 1];			// tmp[i] = c(len, i)
		tmp[0] = 1;	
		for (int j = 1; j <= min(n, len); ++j)
			tmp[j] = Mul(Mul(tmp[j - 1], len - j + 1), inv[j]);
		
		for (int j = 1; j <= n; ++j)					// j schools can send, including the current one
			for (int k = 1; k <= min(j, len); ++k)		// k schools actually sent, including the current one
				Add(g[i][j], Mul(c[j - 1][k - 1], tmp[k]));
	}
}

void Solve()
{
	int res = 0;
	fill(f[0], f[0] + m, 1);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j < m; ++j)
		{
			if (a[i] <= p[j - 1] + 1 && p[j] <= b[i])
			{
				int cnt = 0;							// number of schools that contain range j
				for (int k = i; k >= 1; --k)
				{
					cnt += (a[k] <= p[j - 1] + 1 && p[j] <= b[k]);
					Add(f[i][j], Mul(f[k - 1][j - 1], g[j][cnt]));
				}
				// cout << "f[" << i << "][" << j << "] = " << f[i][j] << '\n';
				Add(res, f[i][j]);
			}
			Add(f[i][j], f[i][j - 1]);
		}
	cout << res;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) 
	{
		cin >> a[i] >> b[i];
		p[m++] = a[i] - 1;
		p[m++] = b[i];
	}
	sort(p, p + m);
	m = unique(p, p + m) - p;
	Prep();
	Solve();
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 5464 KB Output is correct
2 Correct 202 ms 5464 KB Output is correct
3 Correct 204 ms 5464 KB Output is correct
4 Correct 206 ms 5476 KB Output is correct
5 Correct 202 ms 5596 KB Output is correct
6 Correct 225 ms 5596 KB Output is correct
7 Correct 206 ms 5720 KB Output is correct
8 Correct 266 ms 5728 KB Output is correct
9 Correct 215 ms 5888 KB Output is correct
10 Correct 205 ms 5888 KB Output is correct
11 Correct 239 ms 5888 KB Output is correct
12 Correct 295 ms 5888 KB Output is correct
13 Correct 221 ms 5888 KB Output is correct
14 Correct 214 ms 5888 KB Output is correct
15 Correct 202 ms 5888 KB Output is correct
16 Correct 60 ms 5888 KB Output is correct
17 Correct 48 ms 5888 KB Output is correct
18 Correct 49 ms 5888 KB Output is correct
19 Correct 64 ms 5888 KB Output is correct
20 Correct 43 ms 5888 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 5464 KB Output is correct
2 Correct 202 ms 5464 KB Output is correct
3 Correct 204 ms 5464 KB Output is correct
4 Correct 206 ms 5476 KB Output is correct
5 Correct 202 ms 5596 KB Output is correct
6 Correct 225 ms 5596 KB Output is correct
7 Correct 206 ms 5720 KB Output is correct
8 Correct 266 ms 5728 KB Output is correct
9 Correct 215 ms 5888 KB Output is correct
10 Correct 205 ms 5888 KB Output is correct
11 Correct 239 ms 5888 KB Output is correct
12 Correct 295 ms 5888 KB Output is correct
13 Correct 221 ms 5888 KB Output is correct
14 Correct 214 ms 5888 KB Output is correct
15 Correct 202 ms 5888 KB Output is correct
16 Correct 60 ms 5888 KB Output is correct
17 Correct 48 ms 5888 KB Output is correct
18 Correct 49 ms 5888 KB Output is correct
19 Correct 64 ms 5888 KB Output is correct
20 Correct 43 ms 5888 KB Output is correct
21 Incorrect 741 ms 5888 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 5464 KB Output is correct
2 Correct 202 ms 5464 KB Output is correct
3 Correct 204 ms 5464 KB Output is correct
4 Correct 206 ms 5476 KB Output is correct
5 Correct 202 ms 5596 KB Output is correct
6 Correct 225 ms 5596 KB Output is correct
7 Correct 206 ms 5720 KB Output is correct
8 Correct 266 ms 5728 KB Output is correct
9 Correct 215 ms 5888 KB Output is correct
10 Correct 205 ms 5888 KB Output is correct
11 Correct 239 ms 5888 KB Output is correct
12 Correct 295 ms 5888 KB Output is correct
13 Correct 221 ms 5888 KB Output is correct
14 Correct 214 ms 5888 KB Output is correct
15 Correct 202 ms 5888 KB Output is correct
16 Correct 60 ms 5888 KB Output is correct
17 Correct 48 ms 5888 KB Output is correct
18 Correct 49 ms 5888 KB Output is correct
19 Correct 64 ms 5888 KB Output is correct
20 Correct 43 ms 5888 KB Output is correct
21 Incorrect 741 ms 5888 KB Output isn't correct
22 Halted 0 ms 0 KB -