oj.uz

Submission #108271

# Submission time Handle Problem Language Result Execution time Memory
108271 2019-04-28T12:09:15 Z polyfish Boat (APIO16_boat) C++14
58 / 100
 2000 ms 23260 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 = 1002;
const int MOD = 1000000007;

int n, l[MAX_N], r[MAX_N];
vector<pair<int, int> > seg;
int64_t C1[MAX_N][MAX_N], C2[MAX_N][MAX_N];
int64_t inv[MAX_N], inv_fact[MAX_N], f[MAX_N][MAX_N], P[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 % MOD;

	return res * inv_fact[k] % MOD;
}

bool contain(int u, int v, int l, int r) {
	return (u<=l && r<=v);
}

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]) % 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 (contain(l[k], r[k], seg[j].first, seg[j].second)) {
					++cnt;
					// if (i==3 && j==1 && k==1)
					// 	debug(tmp);
					f[i][j] = (f[i][j] + f[k-1][j-1] * P[j][cnt]) % 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:39: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:90:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<seg.size(); ++i)
                ~^~~~~~~~~~~
boat.cpp:98:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1; j<seg.size(); ++j) {
                 ~^~~~~~~~~~~
boat.cpp:95: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 1271 ms 23260 KB Output is correct
2 Correct 1228 ms 23132 KB Output is correct
3 Correct 1225 ms 23120 KB Output is correct
4 Correct 1258 ms 23008 KB Output is correct
5 Correct 1211 ms 23032 KB Output is correct
6 Correct 1053 ms 23088 KB Output is correct
7 Correct 1056 ms 23144 KB Output is correct
8 Correct 1109 ms 23132 KB Output is correct
9 Correct 1075 ms 23096 KB Output is correct
10 Correct 1103 ms 23160 KB Output is correct
11 Correct 1040 ms 23064 KB Output is correct
12 Correct 1112 ms 22980 KB Output is correct
13 Correct 1103 ms 23160 KB Output is correct
14 Correct 1067 ms 23164 KB Output is correct
15 Correct 1080 ms 22964 KB Output is correct
16 Correct 226 ms 8952 KB Output is correct
17 Correct 249 ms 9080 KB Output is correct
18 Correct 239 ms 9052 KB Output is correct
19 Correct 264 ms 9164 KB Output is correct
20 Correct 241 ms 8952 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1271 ms 23260 KB Output is correct
2 Correct 1228 ms 23132 KB Output is correct
3 Correct 1225 ms 23120 KB Output is correct
4 Correct 1258 ms 23008 KB Output is correct
5 Correct 1211 ms 23032 KB Output is correct
6 Correct 1053 ms 23088 KB Output is correct
7 Correct 1056 ms 23144 KB Output is correct
8 Correct 1109 ms 23132 KB Output is correct
9 Correct 1075 ms 23096 KB Output is correct
10 Correct 1103 ms 23160 KB Output is correct
11 Correct 1040 ms 23064 KB Output is correct
12 Correct 1112 ms 22980 KB Output is correct
13 Correct 1103 ms 23160 KB Output is correct
14 Correct 1067 ms 23164 KB Output is correct
15 Correct 1080 ms 22964 KB Output is correct
16 Correct 226 ms 8952 KB Output is correct
17 Correct 249 ms 9080 KB Output is correct
18 Correct 239 ms 9052 KB Output is correct
19 Correct 264 ms 9164 KB Output is correct
20 Correct 241 ms 8952 KB Output is correct
21 Correct 942 ms 21628 KB Output is correct
22 Correct 906 ms 21992 KB Output is correct
23 Correct 982 ms 21740 KB Output is correct
24 Correct 839 ms 21464 KB Output is correct
25 Correct 1031 ms 21492 KB Output is correct
26 Correct 1040 ms 21240 KB Output is correct
27 Correct 1012 ms 21604 KB Output is correct
28 Correct 1141 ms 21292 KB Output is correct
29 Correct 1102 ms 21156 KB Output is correct
30 Correct 1082 ms 23032 KB Output is correct
31 Correct 1042 ms 23060 KB Output is correct
32 Correct 1055 ms 23028 KB Output is correct
33 Correct 1071 ms 23032 KB Output is correct
34 Correct 1033 ms 23100 KB Output is correct
35 Correct 1217 ms 23032 KB Output is correct
36 Correct 1275 ms 23160 KB Output is correct
37 Correct 1241 ms 23160 KB Output is correct
38 Correct 1193 ms 23032 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3200 KB Output is correct
2 Correct 18 ms 3200 KB Output is correct
3 Correct 18 ms 3228 KB Output is correct
4 Correct 19 ms 3200 KB Output is correct
5 Correct 19 ms 3328 KB Output is correct
6 Correct 19 ms 3200 KB Output is correct
7 Correct 21 ms 3200 KB Output is correct
8 Correct 18 ms 3248 KB Output is correct
9 Correct 18 ms 3288 KB Output is correct
10 Correct 18 ms 3200 KB Output is correct
11 Correct 18 ms 3192 KB Output is correct
12 Correct 19 ms 3328 KB Output is correct
13 Correct 19 ms 3200 KB Output is correct
14 Correct 19 ms 3200 KB Output is correct
15 Correct 17 ms 3200 KB Output is correct
16 Correct 11 ms 2432 KB Output is correct
17 Correct 10 ms 2304 KB Output is correct
18 Correct 11 ms 2304 KB Output is correct
19 Correct 11 ms 2432 KB Output is correct
20 Correct 10 ms 2304 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1271 ms 23260 KB Output is correct
2 Correct 1228 ms 23132 KB Output is correct
3 Correct 1225 ms 23120 KB Output is correct
4 Correct 1258 ms 23008 KB Output is correct
5 Correct 1211 ms 23032 KB Output is correct
6 Correct 1053 ms 23088 KB Output is correct
7 Correct 1056 ms 23144 KB Output is correct
8 Correct 1109 ms 23132 KB Output is correct
9 Correct 1075 ms 23096 KB Output is correct
10 Correct 1103 ms 23160 KB Output is correct
11 Correct 1040 ms 23064 KB Output is correct
12 Correct 1112 ms 22980 KB Output is correct
13 Correct 1103 ms 23160 KB Output is correct
14 Correct 1067 ms 23164 KB Output is correct
15 Correct 1080 ms 22964 KB Output is correct
16 Correct 226 ms 8952 KB Output is correct
17 Correct 249 ms 9080 KB Output is correct
18 Correct 239 ms 9052 KB Output is correct
19 Correct 264 ms 9164 KB Output is correct
20 Correct 241 ms 8952 KB Output is correct
21 Correct 942 ms 21628 KB Output is correct
22 Correct 906 ms 21992 KB Output is correct
23 Correct 982 ms 21740 KB Output is correct
24 Correct 839 ms 21464 KB Output is correct
25 Correct 1031 ms 21492 KB Output is correct
26 Correct 1040 ms 21240 KB Output is correct
27 Correct 1012 ms 21604 KB Output is correct
28 Correct 1141 ms 21292 KB Output is correct
29 Correct 1102 ms 21156 KB Output is correct
30 Correct 1082 ms 23032 KB Output is correct
31 Correct 1042 ms 23060 KB Output is correct
32 Correct 1055 ms 23028 KB Output is correct
33 Correct 1071 ms 23032 KB Output is correct
34 Correct 1033 ms 23100 KB Output is correct
35 Correct 1217 ms 23032 KB Output is correct
36 Correct 1275 ms 23160 KB Output is correct
37 Correct 1241 ms 23160 KB Output is correct
38 Correct 1193 ms 23032 KB Output is correct
39 Correct 17 ms 3200 KB Output is correct
40 Correct 18 ms 3200 KB Output is correct
41 Correct 18 ms 3228 KB Output is correct
42 Correct 19 ms 3200 KB Output is correct
43 Correct 19 ms 3328 KB Output is correct
44 Correct 19 ms 3200 KB Output is correct
45 Correct 21 ms 3200 KB Output is correct
46 Correct 18 ms 3248 KB Output is correct
47 Correct 18 ms 3288 KB Output is correct
48 Correct 18 ms 3200 KB Output is correct
49 Correct 18 ms 3192 KB Output is correct
50 Correct 19 ms 3328 KB Output is correct
51 Correct 19 ms 3200 KB Output is correct
52 Correct 19 ms 3200 KB Output is correct
53 Correct 17 ms 3200 KB Output is correct
54 Correct 11 ms 2432 KB Output is correct
55 Correct 10 ms 2304 KB Output is correct
56 Correct 11 ms 2304 KB Output is correct
57 Correct 11 ms 2432 KB Output is correct
58 Correct 10 ms 2304 KB Output is correct
59 Correct 1836 ms 23204 KB Output is correct
60 Correct 1610 ms 22984 KB Output is correct
61 Correct 1599 ms 23108 KB Output is correct
62 Correct 1861 ms 23100 KB Output is correct
63 Correct 1849 ms 23160 KB Output is correct
64 Execution timed out 2052 ms 23032 KB Time limit exceeded
65 Halted 0 ms 0 KB -