Submission #406639

#	Time	Username	Problem	Language	Result	Execution time	Memory
406639		gevacrt	Boat (APIO16_boat)	C++17	9 / 100	2076 ms	4384 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 MULT(){return 1;}
template<typename T, typename... Args>
int MULT(T v, Args... args){
    return (v*MULT(args...))%MOD;
}

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;
}
constexpr int fac(int n){
    if(n == 0) return 1;
    return MULT(n, fac(n-1));
}
int nCk(int n, int k){
    int v = binexp(fac(k), MOD-2);
    while(k--){
        v = MULT(v, n);
        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++)
            v += MULT(nCk(B[c]-B[c-1], k+1), nCk(cnt, k), solve(x-1, c-1)), v %= MOD;

        cnt++;
    }

    return v;
}

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

    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: 0 / 27
• Subtask 4: 0 / 42