Submission #1168509

#TimeUsernameProblemLanguageResultExecution timeMemory
1168509AgageldiBoat (APIO16_boat)C++20
0 / 100
2095 ms500 KiB
#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);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...