Submission #82424

#	Time	Username	Problem	Language	Result	Execution time	Memory
82424		Bodo171	Boat (APIO16_boat)	C++14	0 / 100	6 ms	384 KiB

boat

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=505;
const long long mod=1000*1000*1000+7;
long long fact[nmax],inv[nmax],dp[nmax],C[nmax],sum[nmax],combi[nmax];
long long cc,ans;
int st[nmax],dr[nmax],v[2*nmax],spec[nmax];
int n,i,nr,j,k;
long long expo(long long A,long long B)
{
    long long ret=1,p2=A;
    for(int p=0;p<=30;p++)
    {
        if(((1<<p)&B))
        {
            ret=(1LL*ret*p2)%mod;
        }
        p2=(1LL*p2*p2)%mod;
    }
    return ret;
}
void precinv()
{
    fact[0]=1;
    for(i=1;i<=n;i++)
        fact[i]=(1LL*fact[i-1]*i)%mod;
    inv[n]=expo(n,mod-2);
    for(long long i=n-1;i>=0;i--)
        inv[i]=(1LL*inv[i+1]*(i+1))%mod;
}
void calcC(int len)
{
    long long F=1;
    C[0]=1;
    for(long long i=len;i>=max(len-n+1,0);i--)
    {
        F=(1LL*F*i);
        C[len-i+1]=(1LL*F*inv[len-i+1])%mod;
    }
}
long long c(int A,int B)
{
    return (1LL*fact[A]*((1LL*inv[B]*inv[A-B])%mod))%mod;
}
int main()
{
   // freopen("data.in","r",stdin);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>st[i]>>dr[i];
        v[++nr]=st[i];
        v[++nr]=dr[i]+1;
    }
    sort(v+1,v+nr+1);
    precinv();
    for(int cnt=1;cnt<2*n;cnt++)
        if(v[cnt]<v[cnt+1])
    {
        nr=0;sum[0]=1;
        for(j=1;j<=n;j++)
        {
            if(st[j]<=v[cnt]&&dr[j]>=v[cnt+1]-1)
                spec[++nr]=j;
            sum[j]=(1LL*sum[j-1]+dp[j])%mod;
        }
        calcC(v[cnt+1]-v[cnt]);
        combi[0]=1;
        for(i=3;i<=nr;i++)
        {
            combi[i]=0;
            for(j=0;j<=i-2;j++)
           {
                combi[i]=(1LL*combi[i]+1LL*c(i-2,j)*C[i])%mod;
           }
        }
        combi[1]=C[1];
        combi[2]=C[2];
        for(int i=1;i<=nr;i++)
          for(int j=i;j<=nr;j++)
        {
            cc=sum[spec[i]-1];
            dp[j]=(dp[j]+1LL*cc*combi[j-i+1])%mod;
        }
        for(i=1;i<=nr;i++)
            C[i]=0;
    }
    for(i=1;i<=n;i++)
        ans=(ans+dp[i])%mod;
    cout<<ans;
    return 0;
}

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