oj.uz

Submission #108266

# Submission time Handle Problem Language Result Execution time Memory
108266 2019-04-28T11:54:32 Z polyfish Boat (APIO16_boat) C++14
27 / 100
 2000 ms 2104 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 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 C(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) {
		int l = seg[i].second - seg[i].first + 1;
		for (int k=1; k<=n; ++k) {
			for (int j=1; j<=k; ++j)
				P[i][k] = (P[i][k] + C(l, j) * C(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:38: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:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<seg.size(); ++i) {
                ~^~~~~~~~~~~
boat.cpp:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<seg.size(); ++i)
                ~^~~~~~~~~~~
boat.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1; j<seg.size(); ++j) {
                 ~^~~~~~~~~~~
boat.cpp:81:10: warning: unused variable 'res' [-Wunused-variable]
  int64_t res = 0;
          ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 2008 KB Output is correct
2 Correct 359 ms 1912 KB Output is correct
3 Correct 336 ms 2040 KB Output is correct
4 Correct 332 ms 2040 KB Output is correct
5 Correct 337 ms 1912 KB Output is correct
6 Correct 339 ms 1960 KB Output is correct
7 Correct 349 ms 1932 KB Output is correct
8 Correct 348 ms 2000 KB Output is correct
9 Correct 339 ms 1912 KB Output is correct
10 Correct 350 ms 2016 KB Output is correct
11 Correct 425 ms 2040 KB Output is correct
12 Correct 345 ms 2104 KB Output is correct
13 Correct 352 ms 1912 KB Output is correct
14 Correct 345 ms 2020 KB Output is correct
15 Correct 345 ms 1912 KB Output is correct
16 Correct 174 ms 1380 KB Output is correct
17 Correct 166 ms 1272 KB Output is correct
18 Correct 173 ms 1208 KB Output is correct
19 Correct 169 ms 1324 KB Output is correct
20 Correct 169 ms 1264 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 820 KB Time limit exceeded
2 Halted 0 ms 0 KB -