Submission #108276

#	Time	Username	Problem	Language	Result	Execution time	Memory
108276		polyfish	Boat (APIO16_boat)	C++14	31 / 100	878 ms	14456 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;
const int64_t INF = 1e18;
const int64_t INF2 = 1e16;

int n, l[MAX_N], r[MAX_N];
vector<pair<int, int> > seg;
int64_t C1[MAX_N][MAX_N], C2[2*MAX_N][MAX_N];
int64_t inv[MAX_N], inv_fact[MAX_N], f[MAX_N][2*MAX_N], P[2*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;
		if (res>INF2)
			res %= MOD;
	}

	return res % MOD * inv_fact[k] % MOD;
}

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];
				if (P[i][k]>INF)
					P[i][k] %= MOD;
			}
			P[i][k] %= 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 (l[k]<=seg[j].first && seg[j].second<=r[k]) {
					++cnt;
					// if (i==3 && j==1 && k==1)
					// 	debug(tmp);
					f[i][j] = (f[i][j] + f[k-1][j-1] * P[j][cnt]);
					if (f[i][j]>INF)
						f[i][j] %= MOD;
				}
			}
			f[i][j] %= 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 (stderr)

boat.cpp: In function 'void init()':
boat.cpp:41: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:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<seg.size(); ++i) {
                ~^~~~~~~~~~~
boat.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<seg.size(); ++i) {
                ~^~~~~~~~~~~
boat.cpp:95:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<seg.size(); ++i)
                ~^~~~~~~~~~~
boat.cpp:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1; j<seg.size(); ++j) {
                 ~^~~~~~~~~~~
boat.cpp:100:10: warning: unused variable 'res' [-Wunused-variable]
  int64_t res = 0;
          ^~~

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