제출 #406641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
406641		gevacrt	Boat (APIO16_boat)	C++17	36 / 100	2083 ms	4420 KiB

boat

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define int ll

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

int binexp(int base, int pow, int M=MOD){
    int res = 1;
    while(pow){
        if(pow & 1) res *= base;
        pow >>= 1, base *= base;
        if(M) base %= M, res %= M;
    }
    return res;
}

vi fac(5e2+10), inv_fac(5e2+10);

int nCk(int n, int k){
    if(n-k < k) k = n-k;

    int v = inv_fac[k];
    while(k--){
        v *= n; v %= MOD;
        n--;
    }
    return v;
}

vii A; vi B; vvi dp;

int solve(int n, int c){
    if(n == -1) return 1;
    if(c == 0) return 1;
    if(dp[n][c] != -1)
        return dp[n][c];

    auto &v = dp[n][c]; v = solve(n, c-1);

    for(int x = n, cnt = 0; x >= 0; x--){
        if(!(A[x].first <= B[c-1] and B[c] <= A[x].second))
            continue;
    
        for(int k = 0; k <= min(cnt, B[c]-B[c-1]-1); k++){
            int val = nCk(B[c]-B[c-1], k+1)*nCk(cnt, k); val %= MOD;
            val *= solve(x-1, c-1), val %= MOD;
            v += val; v %= MOD;
        }

        cnt++;
    }

    return v;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    fac[0] = inv_fac[0] = 1;
    for(int x = 1; x <= 5e2; x++)
        fac[x] = (x*fac[x-1])%MOD,
        inv_fac[x] = binexp(fac[x], MOD-2);

    int N; cin >> N;

    A.resize(N);
    for(auto &[l, r] : A){
        cin >> l >> r; r++;    
        B.push_back(l); B.push_back(r);
    }

    sort(all(B));

    dp.resize(N, vi(B.size(), -1));
    cout << solve(N-1, B.size()-1)-1 << endl;

    return 0;
}

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