Submission #106966

#	Time	Username	Problem	Language	Result	Execution time	Memory
106966		maksim_gaponov	Boat (APIO16_boat)	C++14	0 / 100	6 ms	768 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

const int MOD = 1e9 + 7;

int mod(int x) {
	x %= MOD;
	if (x < 0)
		x += MOD;
	return x;
}

void run() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		// assert(a[i] == b[i]);
	}
	vector<vector<int>> dp(n);
	vector<int> dp0(n);
	for (int i = 0; i < n; ++i) {
		if (i == 0)
			dp0[i] = 1;
		else
			dp0[i] = dp[i - 1].back();
		dp[i].resize(b[i] - a[i] + 1);
		for (int j = a[i]; j <= b[i]; ++j) {
			dp[i][j - a[i]] = 0;
			if (j != a[i]) {
				dp[i][j - a[i]] += dp[i][j - a[i] - 1];
			} else {
				dp[i][j - a[i]] += dp0[i];
			}
			if (i > 0) {
				int val = 0;
				if (j - 1 >= a[i - 1]) {
					if (j - 1 > b[i - 1])
						val = dp[i - 1].back();
					else
						val = dp[i - 1][j - a[i - 1] - 1];
				}
				else {
					val = dp0[i - 1];
				}
				dp[i][j - a[i]] += val;
			} else {
				dp[i][j - a[i]] += 1;
			}
			dp[i][j - a[i]] %= MOD;
		}
	}
	int ans = dp.back().back();
	ans--;
	ans = mod(ans);
	cout << ans << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
}

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