제출 #501355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501355		Abrar_Al_Samit	Boat (APIO16_boat)	C++17	9 / 100	2071 ms	8204 KiB

boat

#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;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42