Submission #158302

#	Time	Username	Problem	Language	Result	Execution time	Memory
158302		maruii	Boat (APIO16_boat)	C++14	100 / 100	771 ms	4588 KiB

boat

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
vector<int> xx(1);
int f[505][1005], s[1005], g[1005][505], A[505], B[505], inv[1005];

int mp(int x, int r) {
	int ret = 1;
	while (r) {
		if (r & 1) ret = 1ll * ret * x % mod;
		x = 1ll * x * x % mod;
		r >>= 1;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> A[i] >> B[i]; B[i]++;
		xx.push_back(A[i]);
		xx.push_back(B[i]);
	}
	sort(xx.begin(), xx.end());
	xx.erase(unique(xx.begin(), xx.end()), xx.end());
	for (int i = 1; i <= N; ++i) inv[i] = mp(i, mod - 2);
	for (int i = 1; i + 1 < xx.size(); ++i) g[i][0] = 1;
	int ans = 0;
	for (int i = 1; i <= N; ++i) {
		f[i][0] = 1;
		for (int j = 1; j + 1 < xx.size(); ++j) {
			if (A[i] <= xx[j] && xx[j + 1] <= B[i]) {
				long long n = xx[j + 1] - xx[j];
				for (int k = i; k; --k) g[j][k] = (g[j][k] + g[j][k - 1] * (n + 1 - k) % mod * inv[k] % mod) % mod;
				for (int k = 1; k <= i; ++k) f[i][j] = (f[i][j] + g[j][k]) % mod;
			}
			else {
				f[i][j] = f[i - 1][j];
			}
			g[j][0] = (g[j - 1][0] + f[i][j - 1]) % mod;
		}
	}
	for (int i = 1; i + 1 < xx.size(); ++i) ans = (ans + f[N][i]) % mod;
	cout << ans;
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:29:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i + 1 < xx.size(); ++i) g[i][0] = 1;
                  ~~~~~~^~~~~~~~~~~
boat.cpp:33:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j + 1 < xx.size(); ++j) {
                   ~~~~~~^~~~~~~~~~~
boat.cpp:45:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i + 1 < xx.size(); ++i) ans = (ans + f[N][i]) % mod;
                  ~~~~~~^~~~~~~~~~~

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