제출 #1312179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312179		HasanV11010238	Boat (APIO16_boat)	C++20	100 / 100	1010 ms	10468 KiB

boat

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll binpow(ll a, ll b){
    ll res = 1;
    while (b != 0){
        if (b % 2 == 1){
            res *= a;
            res %= mod;
            b--;
        }
        else{
            a *= a;
            a %= mod;
            b /= 2;
        }
    }
    return res;
}
vector<ll> f, inv;
ll C(int n, int k){
    if (k > n || k < 0) return 0;
    return f[n] * inv[k] % mod * inv[n - k] % mod;
}
int main(){
    f.assign(1001, 1), inv.assign(1001, 1);
    for (ll i = 1; i <= 1000; i++){
        f[i] = (f[i - 1] * i) % mod;
        inv[i] = binpow(f[i], mod - 2);
    }
    int n;
    cin>>n;
    vector<int> a(n + 1, 0), b(n + 1, 0);
    set<int> se;
    for (int i = 1; i <= n; i++){
        cin>>a[i]>>b[i];
        se.insert(a[i]);
        se.insert(b[i]);
    }
    int m = 0, la = -1;
    vector<vector<ll>> ran, pos;
    for (auto el : se){
        if (la != -1 && la + 1 < el) ran.push_back({la + 1, el - 1});
        ran.push_back({el, el});
        la = el;
    }
    m = ran.size();
    pos.assign(m, vector<ll>(n + 1, 0));
    vector<vector<ll>> c(n + 1, vector<ll>(n + 1, 0));
    for (int i = 0; i <= n; i++){
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++){
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
    for (int i = 0; i < m; i++){
        vector<ll> co(n + 1, 0);
        ll cur = 1, sz = ran[i][1] - ran[i][0] + 1;
        for (int j = 1; j <= n; j++){
            cur = (cur * (sz - j + 1)) % mod;
            cur = (cur * binpow(j, mod - 2)) % mod;
            co[j] = cur;
        }
        for (int j = 1; j <= n; j++){
            for (int k = j; k <= n; k++){
                pos[i][k] = (pos[i][k] + c[k - 1][j - 1] * co[j]) % mod;
            }
        }
    }
    vector<ll> dp(n + 1, 0);
    dp[0] = 1;
    for (int wh = 0; wh < m; wh++){
        for (int i = n; i >= 1; i--){
            if (!(a[i] <= ran[wh][0] && ran[wh][1] <= b[i])) continue;
            ll cn = 0;
            for (int j = i; j >= 1; j--){
                if (a[j] <= ran[wh][0] && ran[wh][1] <= b[j]) cn++;
                dp[i] = (dp[i] + dp[j - 1] * pos[wh][cn]) % mod;
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        ans = (ans + dp[i]) % mod;
    }
    cout<<ans;
}

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