oj.uz

Submission #219854

# Submission time Handle Problem Language Result Execution time Memory
219854 2020-04-06T14:40:45 Z MKopchev Boat (APIO16_boat) C++14
0 / 100
 186 ms 204536 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e3+42,mod=1e9+7;

int my_pow(long long a,int b)
{
    long long ret=1;
    while(b)
    {
        if(b%2)ret=ret*a%mod;
        a=a*a%mod;
        b=b/2;
    }
    return ret;
}

int n;
pair<int,int> inp[nmax];

set< pair<int,int> > seen;

pair<int,int> groups[nmax];
int pointer=0;

int inv[nmax];

int dp[nmax][nmax][2];

int rec(int which_number,int last_used_group,bool can_place_zero)
{
    if(which_number>n)return 1;//properly chosen
    if(last_used_group==pointer&&can_place_zero==0)return 0;//skipped too much

    if(dp[which_number][last_used_group][can_place_zero]!=-1)return dp[which_number][last_used_group][can_place_zero];

    long long ret=0;

    //place zero
    if(can_place_zero)ret=(ret+rec(which_number+1,last_used_group,1))%mod;

    //place non-zero for other group
    ret=(ret+rec(which_number,last_used_group+1,0));//ignore this group

    //place non-zero
    long long mult=1;
    for(int use=which_number;use<=n;use++)
        if(inp[use].first<=groups[last_used_group+1].first&&groups[last_used_group+1].second<=inp[use].second)
        {
            int nums=use-which_number+1,cur_sz=groups[last_used_group+1].second-groups[last_used_group+1].first+1;

            mult=mult*(cur_sz-nums+1)%mod*inv[nums]%mod;

            if(mult==0)break;

            ret=(ret+mult*rec(use+1,last_used_group+1,1))%mod;

            //cout<<"which_number= "<<which_number<<" last_used_group= "<<last_used_group<<" use= "<<use<<" mult= "<<mult<<" finish= "<<rec(use+1,last_used_group+1,1)<<endl;
        }
        else break;
    dp[which_number][last_used_group][can_place_zero]=ret;

    //cout<<which_number<<" "<<last_used_group<<" "<<can_place_zero<<" -> "<<ret<<endl;

    return ret;
}
int main()
{
    memset(dp,-1,sizeof(dp));

    scanf("%i",&n);

    for(int i=1;i<nmax;i++)inv[i]=my_pow(i,mod-2);

    int prv=1e9;
    for(int i=1;i<=n;i++)
    {
        scanf("%i%i",&inp[i].first,&inp[i].second);

        seen.insert({inp[i].first,-1});
        seen.insert({inp[i].second,0});

        prv=min(prv,inp[i].first);
        prv=min(prv,inp[i].second);
    }

    for(auto k:seen)
    {
        int other=k.first+k.second;
        if(prv<=other)
        {
            pointer++;
            groups[pointer]={prv,other};
            prv=other+1;
        }
    }

    //for(int i=1;i<=pointer;i++)cout<<groups[i].first<<" "<<groups[i].second<<endl;

    int out=rec(1,0,1);

    out=(out-1+mod)%mod;

    printf("%i\n",out);
    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
boat.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&inp[i].first,&inp[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 125304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 125304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 204536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 125304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -