Submission #1224326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224326		dosts	Boat (APIO16_boat)	C++17	9 / 100	2094 ms	10468 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 = 2e6+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));
}


void solve() {
    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]+1);
    int nck[n+1][n+1]{},dp[n+1][2*n+5]{},cfs[n+1][2*n+5]{};
    nck[0][0] = 1;
    for (int i=1;i<=n;i++) {
        nck[i][0] = 1;
        for (int j=1;j<=n;j++) {
            nck[i][j] = add(nck[i-1][j-1],nck[i-1][j]);
        }
    }
    sort(all(v));
    vector<pii> ranges;
    for (int i=1;i<big(v);i++) if (v[i-1] <= v[i]-1) ranges.push_back({v[i-1],v[i]-1});
    if (ranges.empty()) ranges.push_back({a[1],b[1]});
    dp[0][0] = 1;
    vi inv(n+1);
    for (int i=0;i<=n;i++) inv[i] = divide(1,i);
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=big(ranges);j++) {
            pii it = ranges[j-1];
            int sel = 1;
            for (int p = 1;p<=i;p++) {
                sel = mult(sel,it.ss-it.ff+1-p+1);
                sel = mult(sel,inv[p]);
                cfs[i][j] = add(cfs[i][j],mult(sel,nck[i-1][p-1]));
            }
        }
    }
    int ans = 0;
    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 = 0;j<i;j++) {
                    if (!cfs[i-j][r]) continue;
                    int prvdp = 0;
                    for (int rp = 0;rp<r;rp++) prvdp = add(prvdp,dp[j][rp]);
                    dp[i][r] = add(dp[i][r],mult(prvdp,cfs[i-j][r]));
                }
            }
            ans = add(ans,dp[i][r]);
        }
    }
    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: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42