oj.uz

답안 #124983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
124983 2019-07-04T09:29:22 Z Mamnoon_Siam Boat (APIO16_boat) C++17
58 / 100
 2000 ms 14456 KB 
#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " = " << x << endl;

using ll = long long;
const int mod = 1e9 + 7;

ll qpow(ll b, ll p) {
	ll ret = 1;
	while(p) {
		if(p & 1) ret = (ret * b) % mod;
		b = (b * b) % mod, p >>= 1;
	} return ret;
}

struct base {
	ll x;
	void fix() {
		if(x < 0 or x >= mod) x %= mod;
		if(x < 0) x += mod;
	}
	base() {x = 0;}
	base(int _x) { x = _x; fix(); }
	base(ll _x) { x = _x; fix(); }
	base operator + (const base &o) const { return base(x + o.x); }
	base operator - (const base &o) const { return base(x - o.x); }
	base operator * (const base &o) const { return base(x * o.x); }
	base operator / (const base &o) const {
		return base(x * qpow(o.x, mod - 2)); }
	friend istream& operator >> (istream &in, base &o) {
		return in >> o.x; }
	friend ostream& operator << (ostream &out, const base &o) {
		return out << o.x; }
	void operator += (const base &o) { (*this) = (*this) + o; }
	void operator -= (const base &o) { (*this) = (*this) - o; }
	void operator *= (const base &o) { (*this) = (*this) * o; }
	void operator /= (const base &o) { (*this) = (*this) / o; }
};

const int maxn = 505;

int n;
int a[maxn], b[maxn];

int N_rng;
int l[maxn << 1], r[maxn << 1];
// bool vis[maxn][maxn << 1];

base inv[maxn];
base dp[maxn << 1][maxn];
/* 	dp[rng][i] = # of ways to distribute [1..i] among [1..rng]
	ranges s.t. i-th school sends positive amount of boats.
 */
base BC[maxn << 1][maxn];	/* BC = nCr for big N = range size, [range][r] */
base SC[maxn][maxn]; 		/* SC = nCr for small N, all pair (N, R) */
base g[maxn << 1][maxn];
/* g[range][k] = \sum{i = 1}^{k} \binom{k - 1}{i - 1} * \binom{range_size}{i} */

int main(int argc, char const *argv[])
{
	cin >> n;
	vector<int> tmp;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		a[i]--;
		tmp.emplace_back(a[i]);
		tmp.emplace_back(b[i]);
	}

	sort(tmp.begin(), tmp.end());
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());

	for(int i = 1; i < tmp.size(); i++) {
		N_rng++;
		l[N_rng] = tmp[i - 1];
		r[N_rng] = tmp[i];
	}

	{ // precalc i^{-1}
		inv[0] = 1;
		for(int i = 1; i <= n; i++) {
			inv[i] = base(1) / i;
		}
	}
	{ // precalc SC[][]
		for(int i = 0; i <= n; i++) {
			SC[i][0] = 1;
		}
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= i; j++) {
				SC[i][j] = SC[i - 1][j] + SC[i - 1][j - 1];
			}
		}
	}
	{ // precalc BC[][]
		for(int i = 1; i <= N_rng; i++) {
			for(int j = 0; j <= n; j++) {
				int sz = r[i] - l[i];
				if(sz < j) {
					BC[i][j] = 0;
				} else {
					BC[i][j] = 1;
					for(int k = 1; k <= j; k++, sz--) {
						BC[i][j] *= inv[k] * sz;
					}
				}
			}
		}
	}
	{ // precalc g[][]
		for(int range = 1; range <= N_rng; range++) {
			for(int k = 1; k <= n; k++) {
				for(int i = 1; i <= k; i++) {
					g[range][k] += SC[k - 1][i - 1] * BC[range][i];
				}
			}
		}
	}
	for(int i = 0; i <= N_rng; i++) {
		dp[i][0] = 1;
	}
	for(int rng = 1; rng <= N_rng; rng++) {
		for(int i = 1; i <= n; i++) {
			dp[rng][i] = dp[rng - 1][i];
			if(a[i] <= l[rng] and r[rng] <= b[i]) {
				int cnt = 0;
				for(int k = i; k >= 1; k--) {
					if(a[k] <= l[rng] and r[rng] <= b[k]) {
						cnt++;
					}
					dp[rng][i] += dp[rng - 1][k - 1] * g[rng][cnt];
				}
			}
		}
	}
  
	base ans = 0;
	for(int i = 1; i <= n; i++) {
		ans += dp[N_rng][i];
	}
	cout << ans << endl;
	return 0;
}

Compilation message

boat.cpp: In function 'int main(int, const char**)':
boat.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < tmp.size(); i++) {
                 ~~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1474 ms 14456 KB Output is correct
2 Correct 1474 ms 14328 KB Output is correct
3 Correct 1461 ms 14368 KB Output is correct
4 Correct 1458 ms 14456 KB Output is correct
5 Correct 1469 ms 14328 KB Output is correct
6 Correct 1461 ms 14456 KB Output is correct
7 Correct 1460 ms 14328 KB Output is correct
8 Correct 1459 ms 14328 KB Output is correct
9 Correct 1458 ms 14428 KB Output is correct
10 Correct 1466 ms 14456 KB Output is correct
11 Correct 1468 ms 14368 KB Output is correct
12 Correct 1461 ms 14364 KB Output is correct
13 Correct 1457 ms 14456 KB Output is correct
14 Correct 1469 ms 14400 KB Output is correct
15 Correct 1469 ms 14400 KB Output is correct
16 Correct 271 ms 14360 KB Output is correct
17 Correct 288 ms 14328 KB Output is correct
18 Correct 276 ms 14328 KB Output is correct
19 Correct 291 ms 14456 KB Output is correct
20 Correct 281 ms 14372 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1474 ms 14456 KB Output is correct
2 Correct 1474 ms 14328 KB Output is correct
3 Correct 1461 ms 14368 KB Output is correct
4 Correct 1458 ms 14456 KB Output is correct
5 Correct 1469 ms 14328 KB Output is correct
6 Correct 1461 ms 14456 KB Output is correct
7 Correct 1460 ms 14328 KB Output is correct
8 Correct 1459 ms 14328 KB Output is correct
9 Correct 1458 ms 14428 KB Output is correct
10 Correct 1466 ms 14456 KB Output is correct
11 Correct 1468 ms 14368 KB Output is correct
12 Correct 1461 ms 14364 KB Output is correct
13 Correct 1457 ms 14456 KB Output is correct
14 Correct 1469 ms 14400 KB Output is correct
15 Correct 1469 ms 14400 KB Output is correct
16 Correct 271 ms 14360 KB Output is correct
17 Correct 288 ms 14328 KB Output is correct
18 Correct 276 ms 14328 KB Output is correct
19 Correct 291 ms 14456 KB Output is correct
20 Correct 281 ms 14372 KB Output is correct
21 Correct 825 ms 14360 KB Output is correct
22 Correct 804 ms 14456 KB Output is correct
23 Correct 780 ms 14360 KB Output is correct
24 Correct 810 ms 14360 KB Output is correct
25 Correct 807 ms 14328 KB Output is correct
26 Correct 932 ms 14456 KB Output is correct
27 Correct 958 ms 14328 KB Output is correct
28 Correct 941 ms 14456 KB Output is correct
29 Correct 936 ms 14456 KB Output is correct
30 Correct 1361 ms 14328 KB Output is correct
31 Correct 1359 ms 14328 KB Output is correct
32 Correct 1374 ms 14456 KB Output is correct
33 Correct 1372 ms 14456 KB Output is correct
34 Correct 1366 ms 14456 KB Output is correct
35 Correct 1348 ms 14456 KB Output is correct
36 Correct 1360 ms 14360 KB Output is correct
37 Correct 1398 ms 14364 KB Output is correct
38 Correct 1361 ms 14456 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 14328 KB Output is correct
2 Correct 39 ms 14456 KB Output is correct
3 Correct 38 ms 14328 KB Output is correct
4 Correct 39 ms 14456 KB Output is correct
5 Correct 39 ms 14328 KB Output is correct
6 Correct 41 ms 14456 KB Output is correct
7 Correct 41 ms 14352 KB Output is correct
8 Correct 41 ms 14328 KB Output is correct
9 Correct 41 ms 14332 KB Output is correct
10 Correct 41 ms 14328 KB Output is correct
11 Correct 39 ms 14356 KB Output is correct
12 Correct 37 ms 14328 KB Output is correct
13 Correct 38 ms 14328 KB Output is correct
14 Correct 38 ms 14328 KB Output is correct
15 Correct 39 ms 14328 KB Output is correct
16 Correct 25 ms 14328 KB Output is correct
17 Correct 25 ms 14328 KB Output is correct
18 Correct 25 ms 14328 KB Output is correct
19 Correct 26 ms 14328 KB Output is correct
20 Correct 26 ms 14328 KB Output is correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1474 ms 14456 KB Output is correct
2 Correct 1474 ms 14328 KB Output is correct
3 Correct 1461 ms 14368 KB Output is correct
4 Correct 1458 ms 14456 KB Output is correct
5 Correct 1469 ms 14328 KB Output is correct
6 Correct 1461 ms 14456 KB Output is correct
7 Correct 1460 ms 14328 KB Output is correct
8 Correct 1459 ms 14328 KB Output is correct
9 Correct 1458 ms 14428 KB Output is correct
10 Correct 1466 ms 14456 KB Output is correct
11 Correct 1468 ms 14368 KB Output is correct
12 Correct 1461 ms 14364 KB Output is correct
13 Correct 1457 ms 14456 KB Output is correct
14 Correct 1469 ms 14400 KB Output is correct
15 Correct 1469 ms 14400 KB Output is correct
16 Correct 271 ms 14360 KB Output is correct
17 Correct 288 ms 14328 KB Output is correct
18 Correct 276 ms 14328 KB Output is correct
19 Correct 291 ms 14456 KB Output is correct
20 Correct 281 ms 14372 KB Output is correct
21 Correct 825 ms 14360 KB Output is correct
22 Correct 804 ms 14456 KB Output is correct
23 Correct 780 ms 14360 KB Output is correct
24 Correct 810 ms 14360 KB Output is correct
25 Correct 807 ms 14328 KB Output is correct
26 Correct 932 ms 14456 KB Output is correct
27 Correct 958 ms 14328 KB Output is correct
28 Correct 941 ms 14456 KB Output is correct
29 Correct 936 ms 14456 KB Output is correct
30 Correct 1361 ms 14328 KB Output is correct
31 Correct 1359 ms 14328 KB Output is correct
32 Correct 1374 ms 14456 KB Output is correct
33 Correct 1372 ms 14456 KB Output is correct
34 Correct 1366 ms 14456 KB Output is correct
35 Correct 1348 ms 14456 KB Output is correct
36 Correct 1360 ms 14360 KB Output is correct
37 Correct 1398 ms 14364 KB Output is correct
38 Correct 1361 ms 14456 KB Output is correct
39 Correct 39 ms 14328 KB Output is correct
40 Correct 39 ms 14456 KB Output is correct
41 Correct 38 ms 14328 KB Output is correct
42 Correct 39 ms 14456 KB Output is correct
43 Correct 39 ms 14328 KB Output is correct
44 Correct 41 ms 14456 KB Output is correct
45 Correct 41 ms 14352 KB Output is correct
46 Correct 41 ms 14328 KB Output is correct
47 Correct 41 ms 14332 KB Output is correct
48 Correct 41 ms 14328 KB Output is correct
49 Correct 39 ms 14356 KB Output is correct
50 Correct 37 ms 14328 KB Output is correct
51 Correct 38 ms 14328 KB Output is correct
52 Correct 38 ms 14328 KB Output is correct
53 Correct 39 ms 14328 KB Output is correct
54 Correct 25 ms 14328 KB Output is correct
55 Correct 25 ms 14328 KB Output is correct
56 Correct 25 ms 14328 KB Output is correct
57 Correct 26 ms 14328 KB Output is correct
58 Correct 26 ms 14328 KB Output is correct
59 Execution timed out 2057 ms 14328 KB Time limit exceeded
60 Halted 0 ms 0 KB -