Submission #985508

#	Time	Username	Problem	Language	Result	Execution time	Memory
985508		zeta7532	Boat (APIO16_boat)	C++17	100 / 100	800 ms	10640 KiB

boat

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = int;
const ll mod = 1e9+7;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)

ll modpow(long long A,ll N){
    long long res=1;
    while(N){
        if(N&1) res=res*A%mod;
        A=A*A%mod;
        N>>=1;
    }
    return res;
}

ll modinv(ll A){return modpow(A,mod-2);}

int main() {
    ll N;
    cin >> N;
    vector<ll> inv(N+1);
    rep(i,N+1) inv[i]=modinv(i);
    vector<ll> A(N),B(N);
    rep(i,N){
        cin >> A[i] >> B[i];
        B[i]++;
    }
    vector<ll> C;
    C.push_back(0),C.push_back(1);
    rep(i,N) C.push_back(A[i]),C.push_back(B[i]);
    sort(all(C));
    C.erase(unique(all(C)),C.end());
    rep(i,N) A[i]=lower_bound(all(C),A[i])-C.begin();
    rep(i,N) B[i]=lower_bound(all(C),B[i])-C.begin();
    ll M=C.size();
    vector<ll> D(M-1);
    rep(i,M-1) D[i]=C[i+1]-C[i];
    vector<vector<vector<ll>>> dp(2,vector<vector<ll>>(M,vector<ll>(N,0)));
    dp[0][0][0]=1;
    vector<vector<vector<ll>>> cum(2,vector<vector<ll>>(M,vector<ll>(N,0)));
    rep(j,M) cum[0][j][0]=1;
    rep(i,N){
        rep(j,M) rep(k,min(N,i+10)) dp[(i+1)%2][j][k]=0;
        for(ll j=A[i];j<B[i];j++){
            long long sumres=0;
            rep(k,N) sumres+=cum[i%2][j-1][k];
            sumres%=mod;
            sumres*=D[j];
            sumres%=mod;
            dp[(i+1)%2][j][0]=sumres;
            rep(k,min(N-1,i+10)){
                if(D[j]<k+2) break;
                long long res=(long long)(cum[i%2][j][k]+mod-cum[i%2][j-1][k])*(long long)(((long long)(D[j]-k-1)*(long long)(inv[k+2]))%mod);
                res%=mod;
                dp[(i+1)%2][j][k+1]=res;
            }
        }
        rep(k,min(N,i+10)){
            long long sum=0;
            rep(j,M){
                sum+=dp[(i+1)%2][j][k];
                cum[(i+1)%2][j][k]=(cum[i%2][j][k]+sum)%mod;
            }
        }
    }
    ll ans=mod-1;
    rep(k,N){
        ans+=cum[N%2][M-1][k];
        if(ans>=mod) ans-=mod;
    }
    cout << ans << endl;
    return 0;
}

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