oj.uz

Submission #257924

# Submission time Handle Problem Language Result Execution time Memory
257924 2020-08-05T04:59:20 Z daniel920712 Boat (APIO16_boat) C++14
0 / 100
 2000 ms 4616 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <time.h>

using namespace std;
long long MOD=1e9+7;
map < pair < long long , long long > , long long > all;
long long N;
long long a[505],b[505];
map < long long , long long > con,r;
set < long long > have;
long long F(long long x,long long y)
{
    long long i;
    if(x==0) return y!=(1e9+5);
    if(all.find(make_pair(x,y))!=all.end()) return all[make_pair(x,y)];
    all[make_pair(x,y)]=F(x-1,y);
    for(auto i:con)
    {
        if(i.first>=a[x]&&r[i.first]<y&&r[i.first]<=b[x])
        {

            all[make_pair(x,y)]+=i.second*F(x-1,i.first)%MOD;
            if(y==r[i.first]+1&&i.second>=3)
            {

                all[make_pair(x,y)]+=(i.second)*(i.second-1)/2*F(x-1,i.first)%MOD;
            }
            //if(i.second<0) printf("aa %lld\n",i.second);
            all[make_pair(x,y)]%=MOD;
        }
    }
    //printf("%lld %lld %lld\n",x,y,all[make_pair(x,y)]);
    return all[make_pair(x,y)];
}
long long F2(long long x,long long y)
{
    long long i;
    //printf("%lld %lld\n",x,y);
    if(x==0) return y!=1e9+5;
    if(all.find(make_pair(x,y))!=all.end()) return all[make_pair(x,y)];
    all[make_pair(x,y)]=F2(x-1,y);
    for(i=a[x];i<=min(b[x],y-1);i++)
    {

        all[make_pair(x,y)]+=F2(x-1,i);

        all[make_pair(x,y)]%=MOD;
    }

    return all[make_pair(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]);
        //b[i]=rand()%100;
        //a[i]=rand()%100;
        //if(a[i]>b[i]) swap(a[i],b[i]);
        //printf("%lld %lld\n",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;
        }
        //printf("%lld %lld\n",*prev(have.lower_bound(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) printf("%lld %lld\n",i.first,i.second);

    printf("%lld\n",F(N,1e9+5));
    //all.clear();
    //printf("%lld\n",F2(N,1e9+5));

    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:17:15: warning: unused variable 'i' [-Wunused-variable]
     long long i;
               ^
boat.cpp: In function 'int main()':
boat.cpp:60:17: warning: unused variable 'M' [-Wunused-variable]
     long long N,M,i;
                 ^
boat.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&N);
     ~~~~~^~~~~~~~~~~
boat.cpp:64: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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 4616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 4616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 4616 KB Time limit exceeded
2 Halted 0 ms 0 KB -