Submission #113461

#	Time	Username	Problem	Language	Result	Execution time	Memory
113461		ansol4328	Boat (APIO16_boat)	C++11	9 / 100	269 ms	4440 KiB

boat

#include<stdio.h>
#include<algorithm>
#include<map>

using namespace std;
typedef long long ll;

ll n, m[505][2];
ll v[1005], inv[505];
ll dp1[505][1005];
map<ll,ll> cont;
const ll MOD=1e9+7;

ll get_mod(ll x, ll y)
{
    if(y==1) return x;
    ll ret=get_mod(x,y/2);
    (ret*=ret)%=MOD;
    if(y%2==1) (ret*=x)%=MOD;
    return ret;
}

int main()
{
    scanf("%lld",&n);
    inv[n]=1;
    for(ll i=1 ; i<=n ; i++)
    {
        scanf("%lld %lld",&m[i][0],&m[i][1]);
        cont[m[i][0]]=0;
        cont[m[i][1]]=0;
        (inv[n]*=i)%=MOD;
    }
    //contracting
    ll cnt=0, contn;
    for(auto it=cont.begin() ; it!=cont.end() ; it++)
    {
        it->second=++cnt;
        v[cnt]=it->first;
    }
    contn=cnt;
    for(ll i=1 ; i<=n ; i++)
    {
        m[i][0]=cont[m[i][0]];
        m[i][1]=cont[m[i][1]];
    }
    //making modular inverse
    inv[n]=get_mod(inv[n],MOD-2);
    for(ll i=n ; i>1 ; i--) inv[i-1]=(inv[i]*i)%MOD;

    //DP
    ll res=0;
    for(ll i=0 ; i<=contn ; i++) dp1[0][i]=1;
    for(ll i=1 ; i<=n ; i++)
    {
        for(ll j=m[i][0] ; j<m[i][1] ; j++)
        {
            ll gap=v[j+1]-v[j];
            ll k1=gap-1, fac1=gap, c=1, s=0;
            for(ll k=i-1 ; k>=0 ; k--) (dp1[i][j]+=(dp1[k][j-1]*gap))%=MOD;
            for(ll k=i-1 ; k>=1 ; k--)
            {
                if(k1<=0) break;
                if(m[k][0]<=j && j+1<=m[k][1])
                {
                    c++;
                    (fac1*=k1)%=MOD;
                    ll comb=(fac1*inv[c])%MOD;
                    (s+=comb)%=MOD;
                    ll val=1;
                    if(j>1) val=dp1[k-1][j-1];
                    (val*=s)%=MOD;
                    (dp1[i][j]+=val)%=MOD;
                    k1--;
                }
            }
        }
        for(ll j=i-1 ; j>=0 ; j--) (dp1[i][m[i][1]]+=dp1[j][m[i][1]-1])%=MOD;
        for(ll j=1 ; j<=contn ; j++)
        {
            (dp1[i][j]+=dp1[i][j-1])%=MOD;
        }
        (res+=dp1[i][contn])%=MOD;
    }
    printf("%lld",res);
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
boat.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld",&m[i][0],&m[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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