Submission #465070

#	Time	Username	Problem	Language	Result	Execution time	Memory
465070		arminatarod	Boat (APIO16_boat)	C++17	58 / 100	2087 ms	12280 KiB

boat

#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 1005;

constexpr int MAXINT = 1073741823;

constexpr long long int MOD = 1000000007;

pair<long long int, long long int> a[MAXN];

vector<long long int> blocks;

long long int inverted[MAXN];

long long int ways[MAXN][MAXN], dp[MAXN][MAXN];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	inverted[0] = 1;
	inverted[1] = 1;
	for (long long int i = 2; i < MAXN; i++)
		inverted[i] = inverted[MOD % i] * (MOD - MOD / i) % MOD; 
	long long int n, temporary;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].first >> a[i].second;
		blocks.push_back(a[i].first - 1);
		blocks.push_back(a[i].second);
	}
	sort(blocks.begin(), blocks.end());
	blocks.resize(distance(blocks.begin(), unique(blocks.begin(), blocks.end())));
	for (int i = 1; i < blocks.size(); i++) {
		ways[i][0] = 1;
		for (long long int j = 1; j <= n; j++) {
			temporary = blocks[i] - blocks[i - 1];
			for (long long int k = 1; k <= j && k <= blocks[i] - blocks[i - 1]; k++) {
				ways[i][j] = (ways[i][j] + temporary) % MOD;
				temporary = temporary * (blocks[i] - blocks[i - 1] - k) % MOD * inverted[k + 1] % MOD * (j - k) % MOD * inverted[k] % MOD;
			}
		}
	}
	fill(dp[0], dp[0] + MAXN, 1);
	for (int i = 1; i <= n; i++) {
		dp[i][0] = 1;
		for (int j = 1; j < blocks.size(); j++) {
			dp[i][j] = dp[i][j - 1];
			temporary = 1;
			for (int k = i; k >= 0; k--)
				if (a[k].first <= blocks[j - 1] + 1 && blocks[j] <= a[k].second)
					dp[i][j] = (dp[i][j] + dp[k - 1][j - 1] * ways[j][temporary++] % MOD) % MOD;
		}
	}
	cout << dp[n][blocks.size() - 1] - 1;
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 1; i < blocks.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
boat.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int j = 1; j < blocks.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~

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