제출 #501355

#제출 시각아이디문제언어결과실행 시간메모리
501355Abrar_Al_SamitBoat (APIO16_boat)C++17
9 / 100
2071 ms8204 KiB
#include<bits/stdc++.h>
using namespace std;
const int MX = 505;
const int Mod = 1e9 + 7;
int a[MX], b[MX];
map<tuple<int,int,int>,int>dp;
int n;
int solve(int i, int prev, int more) {
    if(i>n) return (prev!=0);
    if(dp.count(make_tuple(i, prev, more))) return dp[make_tuple(i, prev, more)]; 
    int ret = 0;
    ret = solve(i+1, prev, more);
    for(int cur=max(a[i], a[prev]+more+1); cur<=b[i]; ++cur) {
        ret += solve(i+1, i, cur-a[i]);
        if(ret>=Mod) ret -= Mod;
    }
    return dp[make_tuple(i, prev, more)] = ret;
}
void PlayGround() {
    cin >> n;
    for(int i=1; i<=n; ++i) {
        cin >> a[i] >> b[i];
    }   
    cout << solve(1, 0, 0) << endl;

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    PlayGround();
    return 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...