oj.uz

Submission #108269

# Submission time Handle Problem Language Result Execution time Memory
108269 2019-04-28T11:59:44 Z polyfish Boat (APIO16_boat) C++14
27 / 100
 1319 ms 25296 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] = 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[1][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:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1; j<seg.size(); ++j) {
                 ~^~~~~~~~~~~
boat.cpp:93:10: warning: unused variable 'res' [-Wunused-variable]
  int64_t res = 0;
          ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1319 ms 25024 KB Output is correct
2 Correct 1275 ms 25108 KB Output is correct
3 Correct 1289 ms 25092 KB Output is correct
4 Correct 1269 ms 25000 KB Output is correct
5 Correct 1256 ms 25184 KB Output is correct
6 Correct 1062 ms 25052 KB Output is correct
7 Correct 1034 ms 25208 KB Output is correct
8 Correct 1124 ms 25104 KB Output is correct
9 Correct 1056 ms 25200 KB Output is correct
10 Correct 1045 ms 25248 KB Output is correct
11 Correct 1071 ms 24952 KB Output is correct
12 Correct 1137 ms 25156 KB Output is correct
13 Correct 1129 ms 25116 KB Output is correct
14 Correct 1054 ms 25076 KB Output is correct
15 Correct 1096 ms 25296 KB Output is correct
16 Incorrect 241 ms 8956 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1319 ms 25024 KB Output is correct
2 Correct 1275 ms 25108 KB Output is correct
3 Correct 1289 ms 25092 KB Output is correct
4 Correct 1269 ms 25000 KB Output is correct
5 Correct 1256 ms 25184 KB Output is correct
6 Correct 1062 ms 25052 KB Output is correct
7 Correct 1034 ms 25208 KB Output is correct
8 Correct 1124 ms 25104 KB Output is correct
9 Correct 1056 ms 25200 KB Output is correct
10 Correct 1045 ms 25248 KB Output is correct
11 Correct 1071 ms 24952 KB Output is correct
12 Correct 1137 ms 25156 KB Output is correct
13 Correct 1129 ms 25116 KB Output is correct
14 Correct 1054 ms 25076 KB Output is correct
15 Correct 1096 ms 25296 KB Output is correct
16 Incorrect 241 ms 8956 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3684 KB Output is correct
2 Correct 18 ms 3712 KB Output is correct
3 Correct 17 ms 3712 KB Output is correct
4 Correct 20 ms 3584 KB Output is correct
5 Correct 21 ms 3696 KB Output is correct
6 Correct 21 ms 3712 KB Output is correct
7 Correct 20 ms 3712 KB Output is correct
8 Correct 19 ms 3704 KB Output is correct
9 Correct 19 ms 3704 KB Output is correct
10 Correct 24 ms 3712 KB Output is correct
11 Correct 22 ms 3708 KB Output is correct
12 Correct 18 ms 3712 KB Output is correct
13 Correct 19 ms 3712 KB Output is correct
14 Correct 18 ms 3712 KB Output is correct
15 Correct 17 ms 3684 KB Output is correct
16 Correct 11 ms 2432 KB Output is correct
17 Correct 11 ms 2432 KB Output is correct
18 Correct 10 ms 2432 KB Output is correct
19 Correct 12 ms 2432 KB Output is correct
20 Correct 11 ms 2304 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1319 ms 25024 KB Output is correct
2 Correct 1275 ms 25108 KB Output is correct
3 Correct 1289 ms 25092 KB Output is correct
4 Correct 1269 ms 25000 KB Output is correct
5 Correct 1256 ms 25184 KB Output is correct
6 Correct 1062 ms 25052 KB Output is correct
7 Correct 1034 ms 25208 KB Output is correct
8 Correct 1124 ms 25104 KB Output is correct
9 Correct 1056 ms 25200 KB Output is correct
10 Correct 1045 ms 25248 KB Output is correct
11 Correct 1071 ms 24952 KB Output is correct
12 Correct 1137 ms 25156 KB Output is correct
13 Correct 1129 ms 25116 KB Output is correct
14 Correct 1054 ms 25076 KB Output is correct
15 Correct 1096 ms 25296 KB Output is correct
16 Incorrect 241 ms 8956 KB Output isn't correct
17 Halted 0 ms 0 KB -