Submission #1228678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228678		tapilyoca	Boat (APIO16_boat)	C++20	0 / 100	2 ms	576 KiB

boat

/***********************************************
* auth: tapilyoca                              *
* date: 06/29/2025 at 19:58:10                 *
* dots: https://github.com/tapilyoca/dotilyoca * 
***********************************************/

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define dbg(x) if(1) cerr << #x << ": " << x << endl;

/***********************************************/

void solve() {
    ll n;
    cin >> n;
    vec<pll> boatRanges(n);
    
    ll mxy = -1;
    for(int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        boatRanges[i] = {x,y};
        mxy = max(mxy,y);
    }

    vec<vec<ll>> dp(n,vec<ll>(mxy+1,0)); // dp[i][p] = ans up to i assuming person i sends out p

    for(int p = boatRanges[0].first; p <= boatRanges[0].second; p++) {
        dp[0][p] = 1;
    }
    dp[0][0] = 1;

    for(int i = 1; i < n; i++) {
        for(int p = boatRanges[i].first; p <= boatRanges[i].second; p++) {
            ll ways = 0;
            for(int j = 0; j < p; j++) {
                ways += dp[i-1][j];
                ways %= MOD;
            }
            dp[i][p] = ways;
        }

        // special case: dont send. answer is just sum of previous row
        ll sum = 0;
        for(int j = 0; j <= mxy; j++) {
            sum += dp[i-1][j];
            sum %= MOD;
        }
        dp[i][0] = sum;
    }

    ll ans = 0;
    for(ll &x : dp[n-1]) {
        ans += x;
        ans %= MOD;
    }

    // cerr << "DP: " << endl;
    // for(vll &x : dp){ 
    //     for(ll &y : x) {
    //         cerr << y << " ";
    //     } cerr << endl;
    // }

    cout << ans - 1 << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;

    while(t--) {
        solve();
    }

    return 0;
}

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