Submission #1228820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228820		tapilyoca	Boat (APIO16_boat)	C++20	100 / 100	416 ms	8408 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;

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

ll modpow(ll x, ll y) {
    x %= MOD;
    ll out = 1;
    while(y) {
        if(y & 1) out = (out * x) % MOD;
        x = (x * x) % MOD;
        y >>= 1;
    }
    return out;
}

ll invert(ll p) {
    return modpow(p,MOD-2);
}

void solve() {
    ll n;
    cin >> n;
    vll starts(n+1,0), ends(n+1,0);
    set<ll> bounds;
    
    for(int i = 1; i <= n; i++) {
        cin >> starts[i] >> ends[i];
        starts[i]--; // so relevant[i] - relevant[i-1] is full range always
        bounds.insert(starts[i]);
        bounds.insert(ends[i]);
    }

    vll relevant(bounds.begin(),bounds.end());
    ll P = relevant.size();
    ll N = n; 

    // precomp range choose inverse thing
    // O(n^2)
    vvll choose(P+1,vll(N+1,1));
    for(int i = 1; i < P; i++) {
        choose[i][1] = relevant[i] - relevant[i-1];
        choose[i][1] %= MOD;
        for(int j = 2; j <= N; j++) {
            //comb(n,k) = comb(n,k-1) * (n+k-1)/k
            choose[i][j] = ((choose[i][j-1] * (choose[i][1] + j - 1)) % MOD * (invert(j))) % MOD;
            // cerr << i << " " << j << endl;
        }
    }

    // for(int i = 1; i < P; i++) {
    //     for(int j = 1; j <= N; j++) {
    //         cerr << relevant[i] - relevant[i-1] << " choose " << j << " is " << choose[i][j] << endl;
    //     }
    // }

    // cerr << "precomp done" << endl;
    vvll dp(N+1,vll(P+1,0)); // ans up to i assuming the ith school sends out <= relevant[j]

    for(int p = 0; p < P; p++) dp[0][p] = 1;
    
    for(int i = 1; i <= N; i++) {
        dp[i][0] = 1; // only possible if nobody has sent out anything
        for(int p = 1; p < P; p++) {
            
            dp[i][p] = dp[i][p-1];
            ll senders = 0;

            for(int k = i-1; k >= 0; k--) {
                if(relevant[p] <= starts[k+1] or ends[k+1] < relevant[p]) continue;
                // k can send
                senders++;
                dp[i][p] += dp[k][p-1] * choose[p][senders];
                dp[i][p] %= MOD;
            }
        }
    }

    // cerr << "dp" << endl;
    // for(int i = 0; i <= N; i++) {
    //     for(int j = 0; j < P; j++) {
    //         cerr << dp[i][j] << " ";
    //     } cerr << endl;
    // }

    cout << (dp[N][P-1]-1 + MOD) % MOD << endl;
}

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

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

    return 0;
}

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