Submission #1168879

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

boat

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

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

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

int solve(int x,int mx) {
	if(x == n + 1) {
		if(!mx) return 0;
		return 1;
	}
	if(dp.find({x,mx}) != dp.end() && dp[{x,mx}] >= mx) return dp[{x,mx}];
	int var = solve(x + 1, mx);
	for(int i = max(mx, a[x]); i <= b[x]; i++) {
		var += solve(x + 1, i + 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