Submission #259030

#	Time	Username	Problem	Language	Result	Execution time	Memory
259030		daniel920712	Boat (APIO16_boat)	C++14	0 / 100	175 ms	153324 KiB

boat

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <time.h>

using namespace std;
long long MOD=1e9+7;
long long DP[505][505][505];
long long CCon[505];
long long Con2[505];
long long xxx[505];
bool use[505][505][505]={0};
long long cha[505],Con[505],R[505];
map < long long , long long > all;
long long N,now=0;
long long a[505],b[505];
map < long long , long long > con,r;
set < long long > have;

long long Pow(long long a,long long b)
{
    if(b==0) return 1;
    long long t=Pow(a,b/2);
    t*=t;
    t%=MOD;
    if(b%2) t*=a;
    return t%MOD;
}
long long C(long long x,long long y)
{
    return CCon[x]*Con2[y]%MOD*Con2[x-y]%MOD;
}
long long F(long long x,long long y,long long z)
{
    long long i,j,k,tt,ttt=0,aa=1;
    if(x==0) return y!=(now);
    if(use[x][y][z]) return DP[x][y][z];
    use[x][y][z]=1;
    DP[x][y][z]=F(x-1,y,z);
    if(cha[y]>=a[x]&&R[y]<cha[y]&&R[y]<=b[x])
    {
        if(z)
        {
            DP[x][y][z]+=z*Pow(Con[y]-z+1,MOD-2)%MOD*F(x-1,y,z-1)%MOD;
            DP[x][y][z]%=MOD;
        }
    }
    for(i=0;i<y;i++)
    {
        if(!(cha[i]>=a[x]&&R[i]<cha[y]&&R[i]<=b[x])) continue;
        ttt=0;
        DP[x][y][z]+=Con[i]*F(x-1,i,Con[i]-1)%MOD;
        DP[x][y][z]%=MOD;
    }
    return DP[x][y][z];
}

int main()
{
    long long N,M,i;
    scanf("%lld",&N);
    CCon[0]=1;
    Con2[0]=1;
    //xxx[0]
    for(i=1;i<=N;i++)
    {
        CCon[i]=CCon[i-1]*i%MOD;
        Con2[i]=Pow(CCon[i],MOD-2);
        xxx[i]=Pow(i,MOD-2);
    }
    for(i=1;i<=N;i++)
    {
        scanf("%lld %lld",&a[i],&b[i]);
        have.insert(a[i]);
        have.insert(a[i]+1);
        have.insert(b[i]);
        have.insert(b[i]+1);
    }
    for(auto i:have)
    {
        if(i==*prev(have.end()))
        {
            con[i]=1;
            r[i]=i;
        }
        if(have.lower_bound(i)!=have.begin())
        {
            con[*prev(have.lower_bound(i))]=i-*prev(have.lower_bound(i));
            r[*prev(have.lower_bound(i))]=i-1;
        }
    }
    for(auto i:con)
    {
        cha[now]=i.first;
        Con[now]=i.second;
        R[now]=r[i.first];
        now++;
    }
    cha[now]=1e9+5;
    Con[now]=0;
    R[now]=2e9;
    printf("%lld\n",F(N,now,1));


    return 0;
}
/*
2
32 47
18 78
*/

Compilation message (stderr)

boat.cpp: In function 'long long int F(long long int, long long int, long long int)':
boat.cpp:37:17: warning: unused variable 'j' [-Wunused-variable]
     long long i,j,k,tt,ttt=0,aa=1;
                 ^
boat.cpp:37:19: warning: unused variable 'k' [-Wunused-variable]
     long long i,j,k,tt,ttt=0,aa=1;
                   ^
boat.cpp:37:21: warning: unused variable 'tt' [-Wunused-variable]
     long long i,j,k,tt,ttt=0,aa=1;
                     ^~
boat.cpp:37:24: warning: variable 'ttt' set but not used [-Wunused-but-set-variable]
     long long i,j,k,tt,ttt=0,aa=1;
                        ^~~
boat.cpp:37:30: warning: unused variable 'aa' [-Wunused-variable]
     long long i,j,k,tt,ttt=0,aa=1;
                              ^~
boat.cpp: In function 'int main()':
boat.cpp:62:17: warning: unused variable 'M' [-Wunused-variable]
     long long N,M,i;
                 ^
boat.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&N);
     ~~~~~^~~~~~~~~~~
boat.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld",&a[i],&b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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