Submission #1168879

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