oj.uz

Submission #108268

# Submission time Handle Problem Language Result Execution time Memory
108268 2019-04-28T11:58:54 Z polyfish Boat (APIO16_boat) C++14
27 / 100
 1287 ms 8444 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;

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 Incorrect 1287 ms 8444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1287 ms 8444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3072 KB Output is correct
2 Correct 17 ms 3072 KB Output is correct
3 Correct 20 ms 3328 KB Output is correct
4 Correct 16 ms 3200 KB Output is correct
5 Correct 17 ms 3072 KB Output is correct
6 Correct 18 ms 3200 KB Output is correct
7 Correct 18 ms 3072 KB Output is correct
8 Correct 18 ms 3072 KB Output is correct
9 Correct 18 ms 3072 KB Output is correct
10 Correct 19 ms 3072 KB Output is correct
11 Correct 18 ms 3200 KB Output is correct
12 Correct 20 ms 3064 KB Output is correct
13 Correct 18 ms 3072 KB Output is correct
14 Correct 19 ms 3072 KB Output is correct
15 Correct 17 ms 3076 KB Output is correct
16 Correct 10 ms 2048 KB Output is correct
17 Correct 11 ms 2048 KB Output is correct
18 Correct 10 ms 2176 KB Output is correct
19 Correct 12 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 Incorrect 1287 ms 8444 KB Output isn't correct
2 Halted 0 ms 0 KB -