oj.uz

Submission #82427

# Submission time Handle Problem Language Result Execution time Memory
82427 2018-10-30T14:48:46 Z Bodo171 Boat (APIO16_boat) C++14
0 / 100
 7 ms 688 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=505;
const long long mod=1000*1000*1000+7;
long long fact[nmax],inv[nmax],dp[nmax],C[nmax],sum[nmax],combi[nmax];
long long cc,ans;
int st[nmax],dr[nmax],v[2*nmax],spec[nmax];
int n,i,nr,j,k;
long long expo(long long A,long long B)
{
    long long ret=1,p2=A;
    for(int p=0;p<=30;p++)
    {
        if(((1<<p)&B))
        {
            ret=(1LL*ret*p2)%mod;
        }
        p2=(1LL*p2*p2)%mod;
    }
    return ret;
}
void precinv()
{
    fact[0]=1;
    for(i=1;i<=n;i++)
        fact[i]=(1LL*fact[i-1]*i)%mod;
    inv[n]=expo(fact[n],mod-2);
    for(long long i=n-1;i>=0;i--)
        inv[i]=(1LL*inv[i+1]*(i+1))%mod;
}
void calcC(int len)
{
    long long F=1;
    C[0]=1;
    for(long long i=len;i>=max(len-n+1,0);i--)
    {
        F=(1LL*F*i);
        C[len-i+1]=(1LL*F*inv[len-i+1])%mod;
    }
}
long long c(int A,int B)
{
    return (1LL*fact[A]*((1LL*inv[B]*inv[A-B])%mod))%mod;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>st[i]>>dr[i];
        v[++nr]=st[i];
        v[++nr]=dr[i]+1;
    }
    sort(v+1,v+nr+1);
    precinv();
    for(int cnt=1;cnt<2*n;cnt++)
        if(v[cnt]<v[cnt+1])
    {
        nr=0;sum[0]=1;
        for(j=1;j<=n;j++)
        {
            if(st[j]<=v[cnt]&&dr[j]>=v[cnt+1]-1)
                spec[++nr]=j;
            sum[j]=(1LL*sum[j-1]+dp[j])%mod;
        }
        calcC(v[cnt+1]-v[cnt]);
        combi[0]=1;C[0]=1;
        for(i=3;i<=nr;i++)
        {
            combi[i]=0;
            for(j=0;j<=i-2;j++)
           {
                combi[i]=(1LL*combi[i]+1LL*c(i-2,j)*C[j+2])%mod;
           }
        }
        combi[1]=C[1];
        combi[2]=C[2];
        for(int i=1;i<=nr;i++)
          for(int j=i;j<=nr;j++)
        {
            cc=sum[spec[i]-1];
            dp[spec[j]]=(dp[spec[j]]+1LL*cc*combi[j-i+1])%mod;
        }
        for(i=1;i<=nr;i++)
            C[i]=0;
    }
    for(i=1;i<=n;i++)
        ans=(ans+dp[i])%mod;
    cout<<ans;
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 488 KB Output is correct
3 Correct 6 ms 576 KB Output is correct
4 Correct 7 ms 608 KB Output is correct
5 Correct 7 ms 608 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 6 ms 632 KB Output is correct
12 Correct 6 ms 688 KB Output is correct
13 Correct 6 ms 688 KB Output is correct
14 Correct 6 ms 688 KB Output is correct
15 Correct 6 ms 688 KB Output is correct
16 Incorrect 3 ms 688 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 488 KB Output is correct
3 Correct 6 ms 576 KB Output is correct
4 Correct 7 ms 608 KB Output is correct
5 Correct 7 ms 608 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 6 ms 632 KB Output is correct
12 Correct 6 ms 688 KB Output is correct
13 Correct 6 ms 688 KB Output is correct
14 Correct 6 ms 688 KB Output is correct
15 Correct 6 ms 688 KB Output is correct
16 Incorrect 3 ms 688 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 488 KB Output is correct
3 Correct 6 ms 576 KB Output is correct
4 Correct 7 ms 608 KB Output is correct
5 Correct 7 ms 608 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 6 ms 632 KB Output is correct
12 Correct 6 ms 688 KB Output is correct
13 Correct 6 ms 688 KB Output is correct
14 Correct 6 ms 688 KB Output is correct
15 Correct 6 ms 688 KB Output is correct
16 Incorrect 3 ms 688 KB Output isn't correct
17 Halted 0 ms 0 KB -