Submission #866290

#	Time	Username	Problem	Language	Result	Execution time	Memory
866290		Dec0Dedd	Boat (APIO16_boat)	C++14	100 / 100	420 ms	4448 KiB

boat

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 510;
const int MOD = 1e9+7;

ll a[N], b[N], l[2*N+1], dp[N][2*N+1], iv[N], n;

int main() {
    cin>>n;

    iv[1]=1;
    for (int i=2; i<N; ++i) iv[i]=(iv[MOD%i]*(MOD-MOD/i))%MOD;

    vector<int> v;
    for (int i=1; i<=n; ++i) {
        cin>>a[i]>>b[i];
        v.push_back(a[i]), v.push_back(b[i]+1);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    int sz=v.size();
    for (int i=1; i<=n; ++i) {
        a[i]=upper_bound(v.begin(), v.end(), a[i])-v.begin();
        b[i]=upper_bound(v.begin(), v.end(), b[i])-v.begin();
    }

    for (int i=1; i<sz; ++i) l[i]=v[i]-v[i-1], dp[0][i]=1;
    dp[0][0]=1;

    for (int i=1; i<=n; ++i) {
        for (int j=a[i]; j<=b[i]; ++j) {
            dp[i][j]=(1ll*l[j]*dp[i-1][j-1])%MOD;
            ll c=1, x=l[j]-1;
            for (int k=i-1; k>0; --k) {
                if (a[k] > j || b[k] < j) continue;
                ++c;
                (x=(1ll*x*(l[j]+c-2)%MOD)*iv[c])%=MOD;
                if (x == 0) break;
                (dp[i][j]+=1ll*dp[k-1][j-1]*x)%=MOD;
            }
        } dp[i][0]=1;
        for (int j=1; j<sz; ++j) dp[i][j]=(1ll*dp[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+MOD)%MOD;
    } cout<<(dp[n][sz-1]-1+MOD)%MOD<<"\n";
}

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