제출 #219922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219922		MKopchev	Boat (APIO16_boat)	C++14	100 / 100	1932 ms	13072 KiB

boat

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize ("unroll-loops")

#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 coeff[nmax][nmax];

void rec(int which_number,int last_used_group,bool can_place_zero)
{
    for(int which_number=n+1;which_number>=1;which_number--)
        for(int last_used_group=pointer;last_used_group>=0;last_used_group--)
            for(int can_place_zero=0;can_place_zero<2;can_place_zero++)
            {

    if(which_number>n){dp[which_number][last_used_group][can_place_zero]=1;continue;}//properly chosen
    if(last_used_group==pointer){dp[which_number][last_used_group][can_place_zero]=can_place_zero;continue;}//skipped too much

    long long ret=0;

    //place zero
    if(can_place_zero)ret=(ret+dp[which_number+1][last_used_group][1])%mod;

    //place non-zero for other group
    ret=(ret+dp[which_number][last_used_group+1][0])%mod;//ignore this group

    //place non-zero
    if(inp[which_number].first<=groups[last_used_group+1].first&&groups[last_used_group+1].second<=inp[which_number].second)
    {
        int nums=0;
        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)
            {
                nums++;
                ret=(ret+1LL*coeff[last_used_group+1][nums]*dp[use+1][last_used_group+1][1])%mod;
            }
            //cout<<"which_number= "<<which_number<<" last_used_group= "<<last_used_group<<" use= "<<use<<" mult= "<<coeff[last_used_group+1][nums]<<" can_place_zero= "<<can_place_zero<<" finish= "<<rec(use+1,last_used_group+1,1)<<endl;
        }
    }
    dp[which_number][last_used_group][can_place_zero]=ret;

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

}

int C[nmax][nmax];

int ask_C(int n_,int k_)
{
    if(0>k_||k_>n_)return 0;
    return C[n_][k_];
}

int main()
{
    for(int i=0;i<nmax;i++)
        for(int j=0;j<=i;j++)
            if(j==0||j==i)C[i][j]=1;
            else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;

    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<=n;i++)
        for(int j=1;j<=pointer;j++)
        {
            int le=max(inp[i].first,groups[j].first);
            int ri=min(inp[i].second,groups[j].second);

            if(le>ri)continue;

            assert(le==groups[j].first&&ri==groups[j].second);
        }

    cout<<"---"<<endl;
    for(int i=1;i<=pointer;i++)cout<<groups[i].first<<" "<<groups[i].second<<endl;
    */
    for(int which=1;which<=pointer;which++)
        for(int nums=1;nums<=n;nums++)
        {
            int total=groups[which].second-groups[which].first+1;

            if(nums==1)coeff[which][1]=total;
            else
            {
                long long coeff_help=total;
                for(int zero=nums-2;zero>=0;zero--)
                {
                    if(total<nums-zero)coeff_help=0;
                    else if(total==nums-zero)coeff_help=1;
                    else coeff_help=coeff_help*(total-(nums-zero)+1)%mod*inv[nums-zero]%mod;

                    //cout<<"zero= "<<zero<<" "<<total-(nums-zero)+1<<" , "<<nums-zero<<" actual= "<<inv[nums-zero]<<endl;
                    //cout<<"zero= "<<zero<<" "<<coeff_help<<" "<<ask_C(total,nums-zero)<<endl;

                    //if(coeff_help!=ask_C(total,nums-zero))system("pause");
                    coeff[which][nums]=(coeff[which][nums]+1LL*ask_C(nums-2,zero)*coeff_help)%mod;
                }
            }

            //cout<<which<<" "<<nums<<" -> "<<coeff[which][nums]<<endl;
            //cout<<"---"<<endl;
        }

    rec(1,0,1);

    int out=dp[1][0][1];//rec(1,0,1);

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

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

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'int main()':
boat.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
boat.cpp:99: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: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42