Submission #47634

#	Time	Username	Problem	Language	Result	Execution time	Memory
47634		E869120	Boat (APIO16_boat)	C++14	36 / 100	2045 ms	10624 KiB

boat

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long N, A[509], B[509], nr1[509][509], nr2[1009][509], dp[1009][509], inv[1009], mod = 1000000007; vector<long long>V;

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 60; i++) {
		if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}
long long Div(long long a, long long b, long long m) {
	return (a*modpow(b, m - 2, m)) % m;
}

void init() {
	for (int i = 0; i <= 500; i++) {
		for (int j = 0; j <= 500; j++) {
			if (i == 0 || j == 0) nr1[i][j] = 1;
			else nr1[i][j] = (nr1[i - 1][j] + nr1[i][j - 1]) % mod;
		}
	}
	for (int i = 1; i <= 1000; i++) inv[i] = Div(1, i, mod);
	for (int i = 0; i < V.size() - 1; i++) {
		long long L = V[i + 1] - V[i], S = 1;
		for (int j = 0; j <= 500; j++) {
			if (L < j) break;
			nr2[i][j] = S;
			S *= (L - j); S %= mod;
			S *= inv[j + 1]; S %= mod;
		}
	}
}
long long ncr(long long n, long long r) {
	if (r < 0 || n < r) return 0;
	return nr1[n - r][r];
}
long long solve(long long v, long long pos) {
	long long res = 0;
	for (int i = 1; i <= v; i++) {
		res += ncr(v - 1, i - 1)*nr2[pos][i];
		res %= mod;
	}
	return res;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> B[i]; B[i]++;
		V.push_back(A[i]);
		V.push_back(B[i]);
	}
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	for (int i = 1; i <= N; i++) {
		A[i] = lower_bound(V.begin(), V.end(), A[i]) - V.begin();
		B[i] = lower_bound(V.begin(), V.end(), B[i]) - V.begin();
	}
	init();
	dp[0][1] = 1;
	for (int i = 0; i < V.size() - 1; i++) {
		for (int j = 1; j <= N + 1; j++) {
			if (dp[i][j] == 0) continue;
			dp[i + 1][j] += dp[i][j]; dp[i + 1][j] %= mod;
			int G = 0;
			for (int k = j + 1; k <= N + 1; k++) {
				if (A[k - 1] <= i && i < B[k - 1]) {
					G++;
					dp[i + 1][k] += dp[i][j] * solve(G, i);
					dp[i + 1][k] %= mod;
				}
			}
		}
	}
	long long sum = 0;
	for (int i = 2; i <= N + 1; i++) sum += dp[V.size() - 1][i];
	cout << sum%mod << endl;
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void init()':
boat.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~

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