Submission #108244

#	Time	Username	Problem	Language	Result	Execution time	Memory
108244		polyfish	Boat (APIO16_boat)	C++14	0 / 100	2051 ms	1984 KiB

boat

//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], ps[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=2; k<=n; ++k) {
			for (int j=2; j<=k; ++j)
				P[i][k] = (P[i][k] + C(l, j) * C(k-2, j-2)) % MOD;
		}
	}
	// debug(P[1][1]);

	for (int i=0; i<seg.size(); ++i)
		f[0][i] = ps[0][i] = 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;

			if (contain(l[i], r[i], seg[j].first, seg[j].second)) {
				f[i][j] = (f[i][j] + ps[i-1][j-1] * (seg[j].second-seg[j].first+1)) % MOD;
				++cnt;
			}
			// if (i==3 && j==2)
			// 	debug(f[i][j]);

			for (int k=i-1; 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] + ps[k-1][j-1] * P[j][cnt]) % MOD;
			}
		}
	
		for (int j=0; j<seg.size(); ++j)
			ps[i][j] = (ps[i-1][j] + f[i][j]) % MOD;
	}
	debug(f[3][2]);

	cout << (ps[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 (stderr)

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:105:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<seg.size(); ++j)
                 ~^~~~~~~~~~~
boat.cpp:81:10: warning: unused variable 'res' [-Wunused-variable]
  int64_t res = 0;
          ^~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42