Submission #1168507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168507		Agageldi	Boat (APIO16_boat)	C++20	0 / 100	2095 ms	320 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], dp[100][1000001], ans, vis[100][1000001];

int solve(int x,int mx) {
	if(x == n + 1) {
		return 1;
	}
	// if(vis[x][mx]) 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;
	}
	// vis[x][mx] = 1;
	// 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