oj.uz

Submission #113461

# Submission time Handle Problem Language Result Execution time Memory
113461 2019-05-25T16:12:25 Z ansol4328 Boat (APIO16_boat) C++11
9 / 100
 269 ms 4440 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4352 KB Output is correct
2 Correct 9 ms 4352 KB Output is correct
3 Correct 9 ms 4352 KB Output is correct
4 Correct 14 ms 4344 KB Output is correct
5 Correct 10 ms 4352 KB Output is correct
6 Correct 9 ms 4296 KB Output is correct
7 Correct 9 ms 4352 KB Output is correct
8 Correct 8 ms 4224 KB Output is correct
9 Correct 8 ms 4352 KB Output is correct
10 Correct 7 ms 4224 KB Output is correct
11 Correct 9 ms 4324 KB Output is correct
12 Correct 8 ms 4352 KB Output is correct
13 Correct 8 ms 4352 KB Output is correct
14 Correct 8 ms 4352 KB Output is correct
15 Correct 8 ms 4352 KB Output is correct
16 Correct 5 ms 2688 KB Output is correct
17 Correct 5 ms 2688 KB Output is correct
18 Correct 5 ms 2688 KB Output is correct
19 Correct 5 ms 2688 KB Output is correct
20 Correct 5 ms 2688 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4352 KB Output is correct
2 Correct 9 ms 4352 KB Output is correct
3 Correct 9 ms 4352 KB Output is correct
4 Correct 14 ms 4344 KB Output is correct
5 Correct 10 ms 4352 KB Output is correct
6 Correct 9 ms 4296 KB Output is correct
7 Correct 9 ms 4352 KB Output is correct
8 Correct 8 ms 4224 KB Output is correct
9 Correct 8 ms 4352 KB Output is correct
10 Correct 7 ms 4224 KB Output is correct
11 Correct 9 ms 4324 KB Output is correct
12 Correct 8 ms 4352 KB Output is correct
13 Correct 8 ms 4352 KB Output is correct
14 Correct 8 ms 4352 KB Output is correct
15 Correct 8 ms 4352 KB Output is correct
16 Correct 5 ms 2688 KB Output is correct
17 Correct 5 ms 2688 KB Output is correct
18 Correct 5 ms 2688 KB Output is correct
19 Correct 5 ms 2688 KB Output is correct
20 Correct 5 ms 2688 KB Output is correct
21 Incorrect 269 ms 4440 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4352 KB Output is correct
2 Correct 9 ms 4352 KB Output is correct
3 Correct 9 ms 4352 KB Output is correct
4 Correct 14 ms 4344 KB Output is correct
5 Correct 10 ms 4352 KB Output is correct
6 Correct 9 ms 4296 KB Output is correct
7 Correct 9 ms 4352 KB Output is correct
8 Correct 8 ms 4224 KB Output is correct
9 Correct 8 ms 4352 KB Output is correct
10 Correct 7 ms 4224 KB Output is correct
11 Correct 9 ms 4324 KB Output is correct
12 Correct 8 ms 4352 KB Output is correct
13 Correct 8 ms 4352 KB Output is correct
14 Correct 8 ms 4352 KB Output is correct
15 Correct 8 ms 4352 KB Output is correct
16 Correct 5 ms 2688 KB Output is correct
17 Correct 5 ms 2688 KB Output is correct
18 Correct 5 ms 2688 KB Output is correct
19 Correct 5 ms 2688 KB Output is correct
20 Correct 5 ms 2688 KB Output is correct
21 Incorrect 269 ms 4440 KB Output isn't correct
22 Halted 0 ms 0 KB -