Submission #667405

#	Time	Username	Problem	Language	Result	Execution time	Memory
667405		Mahdi	Boat (APIO16_boat)	C++17	9 / 100	307 ms	7384 KiB

boat

#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=505, M=1e9+7;
int n, m, a[N], b[N], dp[N][2*N], c[2*N][N], en[N][N], h[2*N][N];
vector<int>v;

int tav(int x, int p){
    int res=1;
    while(p){
        if(p&1)
            res=1LL*res*x%M;
        x=1LL*x*x%M;
        p>>=1;
    }
    return res;
}

void pre(){
    en[0][0]=1;
    for(int i=1;i<=n;++i){
        en[i][0]=1;
        for(int j=1;j<=i;++j){
            en[i][j]=en[i-1][j]+en[i-1][j-1];
            if(en[i][j]>=M)
                en[i][j]-=M;
        }
    }
    for(int i=0;i<m;++i){
        int x=v[i+1]-v[i];
        c[i][0]=1;
        for(int j=1;j<=min(n, x);++j){
            c[i][j]=1LL*c[i][j-1]*(x-j+1)%M;
            c[i][j]=1LL*c[i][j]*tav(j, M-2)%M;
        }
    }
    for(int i=0;i<m;++i){
        h[i][1]=c[i][1];
        for(int j=2;j<=n;++j){
            ll z=0;
            for(int k=0;k<=j-2;++k)
                z+=1LL*en[j-2][k]*c[i][k+2]%M;
            h[i][j]=z%M;
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i]>>b[i];
        v.push_back(a[i]);
        v.push_back(b[i]+1);
    }
    sort(all(v));
    v.resize(int(unique(all(v))-v.begin()));
    m=(int)v.size()-1;
    pre();
    for(int i=0;i<m;++i)
        dp[0][i]=1;
    for(int i=1;i<=n;++i){
        ll x=dp[i-1][0];
        if(a[i]<=v[0]){
            for(int j=i;j>=1;--j)
                x+=h[0][i-j+1];
        }
        dp[i][0]=x%M;
        for(int j=1;j<m;++j){
            x=dp[i-1][j]+dp[i][j-1];
            x+=M-dp[i-1][j-1];
            if(a[i]<=v[j] && b[i]+1>=v[j+1]){
                int tt=0;
                for(int k=i;k>=1;--k){
                    if(a[k]<=v[j] && b[k]+1>=v[j+1]){
                        ++tt;
                        x+=1LL*h[j][tt]*dp[k-1][j-1]%M;
                    }
                }
            }
            dp[i][j]=x%M;
        }
    }
    cout<<(dp[n][m-1]+M-1)%M<<'\n';
}

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