Submission #1134944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134944		Hamed_Ghaffari	Boat (APIO16_boat)	C++20	100 / 100	459 ms	4504 KiB

boat

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

typedef long long       ll;
typedef long double     ld;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;

#define X               first
#define Y               second
#define SZ(x)           (int)x.size()
#define all(x)          x.begin(), x.end()
#define mins(a,b)       a = min(a,b)
#define maxs(a,b)       a = max(a,b)
#define pb              push_back
#define Mp              make_pair
#define kill(x)         {cout << x << '\n'; exit(0);}
#define killt(x)        {cout << x << '\n'; return;}
#define md(x)           (((x%MOD)+MOD)%MOD)
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)/2)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;
const ll  MOD = 1e9 + 7;
const int MXN = 1023;
const int LOG = 23;

ll power(ll a, ll b) {
    ll res=1;
    while(b) {
        if(b&1) res = md(res*a);
        a = md(a*a);
        b >>= 1;
    }
    return res;
}
ll I[MXN];
void prep() {
    for(int i=1; i<MXN; i++) I[i] = power(i, MOD-2);
}

int n, l[MXN], r[MXN];
vector<ll> cmp;
ll dp[MXN][MXN];

void Main() {
    prep();
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> l[i] >> r[i];
        cmp.pb(l[i]);
        cmp.pb(++r[i]);
    }
    sort(all(cmp));
    cmp.resize(unique(all(cmp))-cmp.begin());
    int m = SZ(cmp);
    for(int i=0; i<MXN; i++) dp[0][i] = 1;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<m; j++) {
            dp[i][j] = dp[i][j-1];
            if(l[i]>cmp[j-1] || r[i]<cmp[j]) continue;
            int t=0;
            ll C = 1;
            for(int k=i-1; k>=0; k--) {
                if(l[k+1]<=cmp[j-1] && cmp[j]<=r[k+1]) {
                    t++;
                    C = md(C*md((cmp[j]-cmp[j-1]+t-1)*I[t]));
                }
                dp[i][j] = md(dp[i][j] + dp[k][j-1]*C);
            }
        }
    }
    ll ans=0;
    for(int i=1; i<=n; i++)
        ans = md(ans+dp[i][m-1]);
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    return 0;
}

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