oj.uz

답안 #124760

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
124760 2019-07-03T21:31:31 Z Mamnoon_Siam Boat (APIO16_boat) C++17
9 / 100
 1482 ms 14460 KB 
#include <bits/stdc++.h>
using namespace std;

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];

base inv[maxn];
base dp[maxn << 1][maxn];
/* 	dp[rng][i] = # of ways considering [1..rng] ranges and first i
 *	boating schools 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 factorial^{-1}
		inv[0] = 1;
		for(int i = 1; i <= n; i++) {
			inv[i] = inv[i - 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[i] <= l[rng] and r[rng] <= b[i]) {
						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:71: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 1444 ms 14352 KB Output is correct
2 Correct 1438 ms 14360 KB Output is correct
3 Correct 1439 ms 14364 KB Output is correct
4 Correct 1438 ms 14456 KB Output is correct
5 Correct 1437 ms 14364 KB Output is correct
6 Correct 1439 ms 14328 KB Output is correct
7 Correct 1450 ms 14404 KB Output is correct
8 Correct 1448 ms 14364 KB Output is correct
9 Correct 1439 ms 14328 KB Output is correct
10 Correct 1439 ms 14456 KB Output is correct
11 Correct 1482 ms 14460 KB Output is correct
12 Correct 1473 ms 14328 KB Output is correct
13 Correct 1446 ms 14456 KB Output is correct
14 Correct 1446 ms 14360 KB Output is correct
15 Correct 1439 ms 14372 KB Output is correct
16 Correct 270 ms 14328 KB Output is correct
17 Correct 290 ms 14328 KB Output is correct
18 Correct 273 ms 14456 KB Output is correct
19 Correct 285 ms 14456 KB Output is correct
20 Correct 275 ms 14328 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1444 ms 14352 KB Output is correct
2 Correct 1438 ms 14360 KB Output is correct
3 Correct 1439 ms 14364 KB Output is correct
4 Correct 1438 ms 14456 KB Output is correct
5 Correct 1437 ms 14364 KB Output is correct
6 Correct 1439 ms 14328 KB Output is correct
7 Correct 1450 ms 14404 KB Output is correct
8 Correct 1448 ms 14364 KB Output is correct
9 Correct 1439 ms 14328 KB Output is correct
10 Correct 1439 ms 14456 KB Output is correct
11 Correct 1482 ms 14460 KB Output is correct
12 Correct 1473 ms 14328 KB Output is correct
13 Correct 1446 ms 14456 KB Output is correct
14 Correct 1446 ms 14360 KB Output is correct
15 Correct 1439 ms 14372 KB Output is correct
16 Correct 270 ms 14328 KB Output is correct
17 Correct 290 ms 14328 KB Output is correct
18 Correct 273 ms 14456 KB Output is correct
19 Correct 285 ms 14456 KB Output is correct
20 Correct 275 ms 14328 KB Output is correct
21 Incorrect 717 ms 14360 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 14328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1444 ms 14352 KB Output is correct
2 Correct 1438 ms 14360 KB Output is correct
3 Correct 1439 ms 14364 KB Output is correct
4 Correct 1438 ms 14456 KB Output is correct
5 Correct 1437 ms 14364 KB Output is correct
6 Correct 1439 ms 14328 KB Output is correct
7 Correct 1450 ms 14404 KB Output is correct
8 Correct 1448 ms 14364 KB Output is correct
9 Correct 1439 ms 14328 KB Output is correct
10 Correct 1439 ms 14456 KB Output is correct
11 Correct 1482 ms 14460 KB Output is correct
12 Correct 1473 ms 14328 KB Output is correct
13 Correct 1446 ms 14456 KB Output is correct
14 Correct 1446 ms 14360 KB Output is correct
15 Correct 1439 ms 14372 KB Output is correct
16 Correct 270 ms 14328 KB Output is correct
17 Correct 290 ms 14328 KB Output is correct
18 Correct 273 ms 14456 KB Output is correct
19 Correct 285 ms 14456 KB Output is correct
20 Correct 275 ms 14328 KB Output is correct
21 Incorrect 717 ms 14360 KB Output isn't correct
22 Halted 0 ms 0 KB -