Submission #1168509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168509		Agageldi	Boat (APIO16_boat)	C++20	0 / 100	2095 ms	500 KiB

boat

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

#define N 500005
#define ll long long
const int M = 1e9 + 7;

ll n, a[N], b[N], ans;
map <pair<int,int>,int> dp;

int solve(int x,int mx) {
	if(x == n + 1) {
		return 1;
	}
	if(dp.find({x,mx})!=dp.end()) return dp[{x,mx}];
	int var = solve(x + 1, mx);
	for(int j = mx + 1; j <= b[x]; j++) {
		var += solve(x + 1, j + 1);
		var %= M;
	}
	dp[{x,mx}] = var;
	return var;
}

int main () {
	ios::sync_with_stdio(0);cin.tie(0);

	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
	}
	cout << solve(1, 0);
}

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