oj.uz

Submission #257967

# Submission time Handle Problem Language Result Execution time Memory
257967 2020-08-05T06:37:16 Z daniel920712 Boat (APIO16_boat) C++14
0 / 100
 1 ms 512 KB 
#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][2005];
bool use[505][2005]={0};
long long cha[2005],Con[2005],R[2005];
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 a;
    long long t=Pow(a,b/2);
    t*=t;
    t%=MOD;
    if(b%2) t*=a;
    return t%MOD;
}
long long F(long long x,long long y)
{
    long long i,j,now;
    if(x==0) return y!=(1e9+5);
    if(use[x][y]) return DP[x][y];
    use[x][y]=1;
    for(auto i=0;i<now;i++)
    {
        if(cha[i]>=a[x]&&R[i]<y&&R[i]<=b[x])
        {

            now=1;
            for(j=x;j>=1;j--)
            {
                if(cha[i]>=a[j]&&R[i]<y&&R[i]<=b[j])
                {
                    now*=(Con[i]-(x-j));
                    now%=MOD;
                    now*=Pow(x-j+1,MOD-2);
                    now%=MOD;
                    DP[x][y]+=now*F(j-1,cha[i])%MOD;
                    DP[x][y]%=MOD;

                }
                else break;
            }

        }
    }
    DP[x][y];
}

int main()
{
    //freopen("3_01.in","rt",stdin);
    //srand(time(NULL));
    long long N,M,i;
    scanf("%lld",&N);
    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));


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

Compilation message

boat.cpp: In function 'long long int F(long long int, long long int)':
boat.cpp:56:12: warning: statement has no effect [-Wunused-value]
     DP[x][y];
     ~~~~~~~^
boat.cpp:29:15: warning: unused variable 'i' [-Wunused-variable]
     long long i,j,now;
               ^
boat.cpp: In function 'int main()':
boat.cpp:63:17: warning: unused variable 'M' [-Wunused-variable]
     long long N,M,i;
                 ^
boat.cpp: In function 'long long int F(long long int, long long int)':
boat.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
boat.cpp: In function 'int main()':
boat.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&N);
     ~~~~~^~~~~~~~~~~
boat.cpp:67: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]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp: In function 'long long int F(long long int, long long int)':
boat.cpp:33:19: warning: 'now' may be used uninitialized in this function [-Wmaybe-uninitialized]
     for(auto i=0;i<now;i++)
                  ~^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -