oj.uz

Submission #108280

# Submission time Handle Problem Language Result Execution time Memory
108280 2019-04-28T12:26:54 Z polyfish Boat (APIO16_boat) C++14
58 / 100
 2000 ms 14436 KB 
//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "boat"

const int MAX_N = 502;
const int MOD = 1000000007;
const int64_t INF = 1e18;

int n, l[MAX_N], r[MAX_N];
vector<pair<int, int> > seg;
int64_t C1[MAX_N][MAX_N], C2[2*MAX_N][MAX_N];
int64_t inv[MAX_N], inv_fact[MAX_N], f[MAX_N][2*MAX_N], P[2*MAX_N][MAX_N];

void read_input() {
	cin >> n;

	for (int i=1; i<=n; ++i)
		cin >> l[i] >> r[i];
}

void init() {
	vector<int> x;

	for (int i=1; i<=n; ++i) {
		x.push_back(l[i]);
		x.push_back(r[i]+1);
	}

	sort(x.begin(), x.end());
	x.resize(unique(x.begin(), x.end()) - x.begin());

	seg.push_back({0, 0});
	for (int i=0; i+1<x.size(); ++i) {
		seg.push_back({x[i], x[i+1]-1});
		// cerr << seg.back().first << ' ' << seg.back().second << '\n';
	}

	inv[1] = 1;
	inv_fact[0] = inv_fact[1] = 1;
	for (int i=2; i<=n; ++i) {
		inv[i] = MOD - MOD/i*inv[MOD%i]%MOD;
		inv_fact[i] = inv_fact[i-1] * inv[i] % MOD;
	}
	// debug(inv[2]*2%MOD);
}

int64_t comb(int n, int k) {
	if (n<0 || n<k)
		return 0;

	int64_t res = 1;

	for (int i=n-k+1; i<=n; ++i) {
		res = res * i;
		if (res>=MOD)
			res %= MOD;
	}

	return res % MOD * inv_fact[k] % MOD;
}

void dp() {
	for (int i=1; i<seg.size(); ++i) {
		for (int j=1; j<=n; ++j)
			C2[i][j] = comb(seg[i].second - seg[i].first + 1, j);
	}

	for (int i=0; i<=n; ++i)
		C1[i][i] = C1[i][0] = 1;
	for (int i=1; i<=n; ++i) {
		for (int j=1; j<i; ++j)
			C1[i][j] = (C1[i-1][j] + C1[i-1][j-1]) % MOD;
	}

	for (int i=1; i<seg.size(); ++i) {
		for (int k=1; k<=n; ++k) {
			for (int j=1; j<=k; ++j) {
				P[i][k] = (P[i][k] + C2[i][j] * C1[k-1][j-1]);
				if (P[i][k]>INF)
					P[i][k] %= MOD;
			}
			P[i][k] %= MOD;
		}
	}
	// debug(P[1][1]);

	for (int i=0; i<seg.size(); ++i)
		f[0][i] = 1;
	for (int i=0; i<=n; ++i)
		f[i][0] = 1;

	int64_t res = 0;

	for (int i=1; i<=n; ++i) {
		for (int j=1; j<seg.size(); ++j) {
			f[i][j] = f[i][j-1];

			int cnt = 0;

			for (int k=i; k>=1; --k) {
				if (l[k]<=seg[j].first && seg[j].second<=r[k]) {
					++cnt;
					// if (i==3 && j==1 && k==1)
					// 	debug(tmp);
					f[i][j] = (f[i][j] + f[k-1][j-1] * P[j][cnt]);
					if (f[i][j]>INF)
						f[i][j] %= MOD;
				}
			}
			f[i][j] %= MOD;
		}
	}
	// debug(f[3][0]);

	cout << (f[n][seg.size()-1] - 1 + MOD) % MOD;
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);

	read_input();
	init();
	dp();
}

Compilation message

boat.cpp: In function 'void init()':
boat.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i+1<x.size(); ++i) {
                ~~~^~~~~~~~~
boat.cpp: In function 'void dp()':
boat.cpp:70:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<seg.size(); ++i) {
                ~^~~~~~~~~~~
boat.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<seg.size(); ++i) {
                ~^~~~~~~~~~~
boat.cpp:94:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<seg.size(); ++i)
                ~^~~~~~~~~~~
boat.cpp:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1; j<seg.size(); ++j) {
                 ~^~~~~~~~~~~
boat.cpp:99:10: warning: unused variable 'res' [-Wunused-variable]
  int64_t res = 0;
          ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1078 ms 14272 KB Output is correct
2 Correct 1037 ms 14312 KB Output is correct
3 Correct 1086 ms 14248 KB Output is correct
4 Correct 1008 ms 14196 KB Output is correct
5 Correct 998 ms 14200 KB Output is correct
6 Correct 735 ms 14208 KB Output is correct
7 Correct 765 ms 14256 KB Output is correct
8 Correct 802 ms 14196 KB Output is correct
9 Correct 737 ms 14200 KB Output is correct
10 Correct 777 ms 14144 KB Output is correct
11 Correct 804 ms 14328 KB Output is correct
12 Correct 753 ms 14200 KB Output is correct
13 Correct 780 ms 14340 KB Output is correct
14 Correct 755 ms 14192 KB Output is correct
15 Correct 775 ms 14268 KB Output is correct
16 Correct 171 ms 6440 KB Output is correct
17 Correct 185 ms 6656 KB Output is correct
18 Correct 173 ms 6524 KB Output is correct
19 Correct 182 ms 6652 KB Output is correct
20 Correct 186 ms 6476 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1078 ms 14272 KB Output is correct
2 Correct 1037 ms 14312 KB Output is correct
3 Correct 1086 ms 14248 KB Output is correct
4 Correct 1008 ms 14196 KB Output is correct
5 Correct 998 ms 14200 KB Output is correct
6 Correct 735 ms 14208 KB Output is correct
7 Correct 765 ms 14256 KB Output is correct
8 Correct 802 ms 14196 KB Output is correct
9 Correct 737 ms 14200 KB Output is correct
10 Correct 777 ms 14144 KB Output is correct
11 Correct 804 ms 14328 KB Output is correct
12 Correct 753 ms 14200 KB Output is correct
13 Correct 780 ms 14340 KB Output is correct
14 Correct 755 ms 14192 KB Output is correct
15 Correct 775 ms 14268 KB Output is correct
16 Correct 171 ms 6440 KB Output is correct
17 Correct 185 ms 6656 KB Output is correct
18 Correct 173 ms 6524 KB Output is correct
19 Correct 182 ms 6652 KB Output is correct
20 Correct 186 ms 6476 KB Output is correct
21 Correct 725 ms 13532 KB Output is correct
22 Correct 782 ms 13676 KB Output is correct
23 Correct 830 ms 13540 KB Output is correct
24 Correct 843 ms 13448 KB Output is correct
25 Correct 670 ms 13624 KB Output is correct
26 Correct 421 ms 13304 KB Output is correct
27 Correct 520 ms 13364 KB Output is correct
28 Correct 422 ms 13216 KB Output is correct
29 Correct 520 ms 13208 KB Output is correct
30 Correct 735 ms 14328 KB Output is correct
31 Correct 706 ms 14200 KB Output is correct
32 Correct 773 ms 14156 KB Output is correct
33 Correct 715 ms 14200 KB Output is correct
34 Correct 820 ms 14212 KB Output is correct
35 Correct 986 ms 14200 KB Output is correct
36 Correct 1082 ms 14332 KB Output is correct
37 Correct 957 ms 14436 KB Output is correct
38 Correct 957 ms 14220 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2944 KB Output is correct
2 Correct 17 ms 2944 KB Output is correct
3 Correct 19 ms 2944 KB Output is correct
4 Correct 18 ms 2944 KB Output is correct
5 Correct 19 ms 2944 KB Output is correct
6 Correct 15 ms 2944 KB Output is correct
7 Correct 19 ms 2944 KB Output is correct
8 Correct 16 ms 2944 KB Output is correct
9 Correct 18 ms 2944 KB Output is correct
10 Correct 15 ms 2944 KB Output is correct
11 Correct 19 ms 2944 KB Output is correct
12 Correct 19 ms 2944 KB Output is correct
13 Correct 18 ms 2944 KB Output is correct
14 Correct 21 ms 3072 KB Output is correct
15 Correct 21 ms 2944 KB Output is correct
16 Correct 11 ms 2176 KB Output is correct
17 Correct 11 ms 2176 KB Output is correct
18 Correct 10 ms 2176 KB Output is correct
19 Correct 11 ms 2176 KB Output is correct
20 Correct 10 ms 2048 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1078 ms 14272 KB Output is correct
2 Correct 1037 ms 14312 KB Output is correct
3 Correct 1086 ms 14248 KB Output is correct
4 Correct 1008 ms 14196 KB Output is correct
5 Correct 998 ms 14200 KB Output is correct
6 Correct 735 ms 14208 KB Output is correct
7 Correct 765 ms 14256 KB Output is correct
8 Correct 802 ms 14196 KB Output is correct
9 Correct 737 ms 14200 KB Output is correct
10 Correct 777 ms 14144 KB Output is correct
11 Correct 804 ms 14328 KB Output is correct
12 Correct 753 ms 14200 KB Output is correct
13 Correct 780 ms 14340 KB Output is correct
14 Correct 755 ms 14192 KB Output is correct
15 Correct 775 ms 14268 KB Output is correct
16 Correct 171 ms 6440 KB Output is correct
17 Correct 185 ms 6656 KB Output is correct
18 Correct 173 ms 6524 KB Output is correct
19 Correct 182 ms 6652 KB Output is correct
20 Correct 186 ms 6476 KB Output is correct
21 Correct 725 ms 13532 KB Output is correct
22 Correct 782 ms 13676 KB Output is correct
23 Correct 830 ms 13540 KB Output is correct
24 Correct 843 ms 13448 KB Output is correct
25 Correct 670 ms 13624 KB Output is correct
26 Correct 421 ms 13304 KB Output is correct
27 Correct 520 ms 13364 KB Output is correct
28 Correct 422 ms 13216 KB Output is correct
29 Correct 520 ms 13208 KB Output is correct
30 Correct 735 ms 14328 KB Output is correct
31 Correct 706 ms 14200 KB Output is correct
32 Correct 773 ms 14156 KB Output is correct
33 Correct 715 ms 14200 KB Output is correct
34 Correct 820 ms 14212 KB Output is correct
35 Correct 986 ms 14200 KB Output is correct
36 Correct 1082 ms 14332 KB Output is correct
37 Correct 957 ms 14436 KB Output is correct
38 Correct 957 ms 14220 KB Output is correct
39 Correct 18 ms 2944 KB Output is correct
40 Correct 17 ms 2944 KB Output is correct
41 Correct 19 ms 2944 KB Output is correct
42 Correct 18 ms 2944 KB Output is correct
43 Correct 19 ms 2944 KB Output is correct
44 Correct 15 ms 2944 KB Output is correct
45 Correct 19 ms 2944 KB Output is correct
46 Correct 16 ms 2944 KB Output is correct
47 Correct 18 ms 2944 KB Output is correct
48 Correct 15 ms 2944 KB Output is correct
49 Correct 19 ms 2944 KB Output is correct
50 Correct 19 ms 2944 KB Output is correct
51 Correct 18 ms 2944 KB Output is correct
52 Correct 21 ms 3072 KB Output is correct
53 Correct 21 ms 2944 KB Output is correct
54 Correct 11 ms 2176 KB Output is correct
55 Correct 11 ms 2176 KB Output is correct
56 Correct 10 ms 2176 KB Output is correct
57 Correct 11 ms 2176 KB Output is correct
58 Correct 10 ms 2048 KB Output is correct
59 Execution timed out 2047 ms 14192 KB Time limit exceeded
60 Halted 0 ms 0 KB -