제출 #1224266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224266		dosts	Boat (APIO16_boat)	C++20	0 / 100	2 ms	2368 KiB

boat

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 2e3+1, inf = 2e9;

int add(int x,int y) {
    if ((x + y) >= MOD) return x + y - MOD;
    return x + y;
}

int mult(int x,int y) {
    return (1LL * x * y) % MOD;
}

int expo(int x,int y) {
    if (!y) return 1;
    int e = expo(x, y >> 1);
    e = mult(e, e);
    if (y & 1) e = mult(e, x);
    return e;
}
int divide(int x, int y) {
    return mult(x, expo(y, MOD - 2));
}
vi f(LIM), finv(LIM);
int nck(int n, int k) {
    if (n < k || n < 0 || k < 0) return 0;
    return mult(f[n], mult(finv[k], finv[n - k]));
}

void combo() {
    f[0] = 1;
    for (int i = 1; i < LIM; i++) f[i] = mult(f[i - 1], i);
    finv[LIM - 1] = divide(1, f[LIM - 1]);
    for (int i = LIM - 2; i >= 0; i--) finv[i] = mult(finv[i + 1], i + 1);
}

void solve() {
    combo();
    int n;
    cin >> n;
    vi a(n+1),b(n+1);
    vi v;
    for (int i=1;i<=n;i++) cin >> a[i] >> b[i];
    for (int i=1;i<=n;i++) v.push_back(a[i]);
    for (int i=1;i<=n;i++) v.push_back(b[i]);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    vector<pii> ranges;
    ranges.push_back({v[0],v[0]});
    for (int i=0;i<big(v)-1;i++) ranges.push_back({v[i]+1,v[i+1]});
    //for (auto it : ranges) cout << it.ff sp it.ss << '\n';
    int dp[n+1][big(ranges)+1]{};
    for (int i=1;i<=n;i++) {
        for (int r = 1;r<=big(ranges);r++) {
            pii it = ranges[r-1];
            if (it.ff >= a[i] && it.ss <= b[i]) {
                for (int j = 1;j<i;j++) {
                    int prvdp = 0;
                    for (int rp = 1;rp<r;rp++) prvdp = add(prvdp,dp[j][rp]);
                    for (int p = 1;p<=i-j;p++) {
                        int coef = mult(nck(it.ss-it.ff+1,p),nck(i-j-1,p-1));
                        dp[i][r] = add(dp[i][r],mult(prvdp,coef));
                    }
                }
                for (int p = 1;p<=i;p++) {
                    int coef = mult(nck(it.ss-it.ff+1,p),nck(i-1,p-1));
                    dp[i][r] = add(dp[i][r],coef);
                }
            }
            //cout << i sp r sp dp[i][r] << '\n';
        }
    }
    int ans = 0;
    for (int i = 1;i<=n;i++) for (int j = 1;j<=big(ranges);j++) ans = add(ans,dp[i][j]);
    cout << ans << '\n';
}   

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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