Submission #1173529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173529		AlgorithmWarrior	Boat (APIO16_boat)	C++20	100 / 100	741 ms	5380 KiB

boat

#include <bits/stdc++.h>

using namespace std;

int const MOD=1e9+7;
int const MAX=505;
int n;
vector<int>pos;
int a[MAX],b[MAX];
int comb[MAX][MAX];
int inv[MAX];
int combi[MAX]; /// C len,i
int add[2*MAX][MAX];
/// nr de moduri sa adaugam in al i-lea interval
/// j puncte (unde adaugam un subset de la 1 la j-1
/// si pe j sigur)
int dp[2*MAX][MAX];
/// nr de moduri sa adaugam in primele i intervale
/// puncte pana la j (pe j il adaugam sigur)
bool inclus[MAX];

int bin_exp(int base,int exp){
    int rez=1;
    while(exp){
        if(exp&1)
            rez=1LL*rez*base%MOD;
        base=1LL*base*base%MOD;
        exp/=2;
    }
    return rez;
}

void get_comb(){
    comb[0][0]=1;
    int i,j;
    for(i=1;i<=n;++i){
        comb[i][0]=1;
        for(j=1;j<=i;++j)
            comb[i][j]=(comb[i-1][j]+comb[i-1][j-1])%MOD;
    }
    for(i=1;i<=n;++i)
        inv[i]=bin_exp(i,MOD-2);
}

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i){
        cin>>a[i]>>b[i];
        ++b[i];
        pos.push_back(a[i]);
        pos.push_back(b[i]);
    }
    sort(pos.begin(),pos.end());
    auto it=unique(pos.begin(),pos.end());
    pos.resize(distance(pos.begin(),it));
}

void get_add(){
    int intv,i,j;
    for(intv=0;intv<(int)pos.size()-1;++intv){
        int len=pos[intv+1]-pos[intv];
        int rez=1;
        for(i=1;i<=n && i<=len;++i){
            rez=1LL*rez*(len-i+1)%MOD;
            rez=1LL*rez*inv[i]%MOD;
            combi[i]=rez;
        }
        for(i=1;i<=n;++i)
            for(j=0;j<i && j<len;++j)
                add[intv][i]=(add[intv][i]+1LL*comb[i-1][j]*combi[j+1]%MOD)%MOD;
    }
}

void get_dp(){
    int intv,i,j;
    for(intv=0;intv<(int)pos.size()-1;++intv){
        for(i=1;i<=n;++i)
            inclus[i]=(a[i]<=pos[intv] && pos[intv+1]<=b[i]);
        dp[intv][0]=1;
        if(intv){
            for(i=1;i<=n;++i)
                dp[intv][i]=dp[intv-1][i];
            for(i=1;i<=n;++i)
                if(inclus[i]){
                    int cnt=1;
                    for(j=i-1;j>=0;--j){
                        dp[intv][i]=(dp[intv][i]+1LL*dp[intv-1][j]*add[intv][cnt]%MOD)%MOD;
                        cnt+=inclus[j];
                    }
                }
        }
        else{
            int cnt=0;
            for(i=1;i<=n;++i)
                if(inclus[i]){
                    ++cnt;
                    dp[intv][i]=add[intv][cnt];
                }
        }
    }
}

int get_ans(){
    int sum=0;
    int i;
    for(i=1;i<=n;++i)
        sum=(sum+dp[(int)pos.size()-2][i])%MOD;
    return sum;
}

int main()
{
    read();
    get_comb();
    get_add();
    get_dp();
    cout<<get_ans();
    return 0;
}

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