Submission #1292698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292698		goulthen	Boat (APIO16_boat)	C++20	100 / 100	764 ms	8452 KiB

boat

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

#define int long long
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, b, a) for (int i = b; i >= a; --i)
#define pb push_back
#define all(v) (v).begin(), (v).end()

const int MAXN = 5e2+10;
const int MOD = 1e9+7;
int l[MAXN], r[MAXN], dp[MAXN][2*MAXN], ch[2*MAXN][MAXN], ch2[MAXN][MAXN], ifact[MAXN];

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);

    int n;cin >> n;
    ifact[0] = ifact[1] = 1;
    rep(i,2,n) ifact[i] = MOD-(MOD/i)*ifact[MOD%i]%MOD;
    rep(i,1,n) ifact[i] = ifact[i]*ifact[i-1]%MOD;

    vector<int> ev;
    rep(i,1,n) {
        cin >> l[i] >> r[i];
        ev.pb(l[i]);
        ev.pb(r[i]+1);
    }
    ev.pb(0);
    sort(all(ev));
    ev.erase(unique(all(ev)), ev.end());
    int m = ev.size()-1;

    rep(i,1,m-1) {
        ch[i][0] = 1LL;
        rep(j,1,n) {
            int len = ev[i+1]-ev[i];
            ch[i][j] = 1;
            per(k,len+j-2,len-1) ch[i][j] = (ch[i][j]*k)%MOD;
            ch[i][j] = ch[i][j]*ifact[j]%MOD;
        }
    }

    rep(j,0,m)dp[0][j] = 1;
    rep(i,1,n) {
        dp[i][0] = 1;
        rep(j,1,m-1) {
            dp[i][j] = (dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+MOD)%MOD;
            //cout << dp[i][j] << '\n';
            int cnt = 1;
            if(l[i] > ev[j] || r[i] < ev[j+1]-1) continue;
            dp[i][j] = (dp[i][j] + dp[i-1][j-1]*(ev[j+1]-ev[j]))%MOD;
            per(k,i-1,1) {
                if(l[k] <= ev[j] && r[k] >= ev[j+1]-1) {
                    cnt++;
                    dp[i][j] = (dp[i][j] + dp[k-1][j-1]*ch[j][cnt])%MOD;
                }
            }
            //cout << i << ' ' << j << ' ' << dp[i][j]  << '\n';
        }
    }

    cout << dp[n][m-1] -1<< '\n';
}

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