oj.uz

Submission #310024

# Submission time Handle Problem Language Result Execution time Memory
310024 2020-10-05T10:40:36 Z vipghn2003 Boat (APIO16_boat) C++14
0 / 100
 1716 ms 6596 KB 
#include<bits/stdc++.h>
using namespace std;

const int N=505;
const int mod=1e9+7;
int n,l[N],r[N],dp[N][N*2],sum[N][N*2],igt[N],gt[N],ways[N*2][N];

int Power(int x,int n)
{
    if(!n) return 1;
    if(n%2) return 1ll*Power(x,n-1)*x%mod;
    int tmp=Power(x,n/2);
    return 1ll*tmp*tmp%mod;
}

void init()
{
    gt[0]=1;
    for(int i=1;i<=N-5;i++) gt[i]=1ll*gt[i-1]*i%mod;
    igt[N-5]=Power(gt[N-5],mod-2);
    for(int i=N-5-1;i>=0;i--) igt[i]=1ll*igt[i+1]*(i+1)%mod;
}

int C(int k,int n)
{
    if(k<0||k>n) return 0;
    if(n<=500) return 1ll*gt[n]*igt[n-k]%mod*igt[k]%mod;
    int res=igt[k];
    for(int i=n-k+1;i<=n;i++) res=1ll*res*i%mod;
    return res;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    init();
    vector<int>val;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
        r[i]++;
        val.push_back(l[i]);
        val.push_back(r[i]);
    }
    val.push_back(0);
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    for(int i=1;i<=n;i++)
    {
        l[i]=lower_bound(val.begin(),val.end(),l[i])-val.begin();
        r[i]=lower_bound(val.begin(),val.end(),r[i])-val.begin();
    }
    int sz=val.size()-1;
    for(int i=1;i<=sz-1;i++)
    {
        int cur=C(1,val[i+1]-val[i]);
        for(int k=1;k<=n;k++)
        {
            for(int j=k;j<=n;j++) ways[i][j]=(ways[i][j]+1ll*cur*C(k-1,j-1)%mod)%mod;
            cur=1ll*cur*(n-k)%mod;
            cur=1ll*cur*Power(k+1,mod-2)%mod;
        }
    }
    int res=0;
    dp[0][0]=1;
    for(int j=0;j<=sz-1;j++) sum[0][j]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=l[i];j<r[i];j++)
        {
            int cnt=0;
            for(int k=i;k>=1;k--)
            {
                if(val[l[k]]<=val[j]&&val[j+1]<=val[r[k]]);
                else cnt++;
                dp[i][j]=(dp[i][j]+1ll*sum[k-1][j-1]*ways[j][i-k+1-cnt]%mod)%mod;
            }
        }
        for(int j=1;j<=sz-1;j++)
        {
            sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
        }
        res=(res+sum[i][sz-1])%mod;
    }
    cout<<res;
}

Compilation message

boat.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main()
      |      ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1699 ms 6140 KB Output is correct
2 Correct 1688 ms 6136 KB Output is correct
3 Correct 1685 ms 6136 KB Output is correct
4 Correct 1689 ms 6068 KB Output is correct
5 Correct 1690 ms 6136 KB Output is correct
6 Correct 1683 ms 6520 KB Output is correct
7 Correct 1697 ms 6564 KB Output is correct
8 Correct 1683 ms 6264 KB Output is correct
9 Correct 1687 ms 6444 KB Output is correct
10 Correct 1694 ms 6264 KB Output is correct
11 Correct 1689 ms 6596 KB Output is correct
12 Correct 1700 ms 6520 KB Output is correct
13 Correct 1716 ms 6392 KB Output is correct
14 Correct 1694 ms 6520 KB Output is correct
15 Correct 1707 ms 6264 KB Output is correct
16 Incorrect 299 ms 4600 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1699 ms 6140 KB Output is correct
2 Correct 1688 ms 6136 KB Output is correct
3 Correct 1685 ms 6136 KB Output is correct
4 Correct 1689 ms 6068 KB Output is correct
5 Correct 1690 ms 6136 KB Output is correct
6 Correct 1683 ms 6520 KB Output is correct
7 Correct 1697 ms 6564 KB Output is correct
8 Correct 1683 ms 6264 KB Output is correct
9 Correct 1687 ms 6444 KB Output is correct
10 Correct 1694 ms 6264 KB Output is correct
11 Correct 1689 ms 6596 KB Output is correct
12 Correct 1700 ms 6520 KB Output is correct
13 Correct 1716 ms 6392 KB Output is correct
14 Correct 1694 ms 6520 KB Output is correct
15 Correct 1707 ms 6264 KB Output is correct
16 Incorrect 299 ms 4600 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1699 ms 6140 KB Output is correct
2 Correct 1688 ms 6136 KB Output is correct
3 Correct 1685 ms 6136 KB Output is correct
4 Correct 1689 ms 6068 KB Output is correct
5 Correct 1690 ms 6136 KB Output is correct
6 Correct 1683 ms 6520 KB Output is correct
7 Correct 1697 ms 6564 KB Output is correct
8 Correct 1683 ms 6264 KB Output is correct
9 Correct 1687 ms 6444 KB Output is correct
10 Correct 1694 ms 6264 KB Output is correct
11 Correct 1689 ms 6596 KB Output is correct
12 Correct 1700 ms 6520 KB Output is correct
13 Correct 1716 ms 6392 KB Output is correct
14 Correct 1694 ms 6520 KB Output is correct
15 Correct 1707 ms 6264 KB Output is correct
16 Incorrect 299 ms 4600 KB Output isn't correct
17 Halted 0 ms 0 KB -