oj.uz

답안 #310026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310026 2020-10-05T10:42:07 Z vipghn2003 Boat (APIO16_boat) C++14
0 / 100
 1779 ms 6588 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;
            if(k!=1) cur=1ll*cur*Power(k+1,mod-2)%mod;
            else cur=1ll*cur*((mod+1)/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

# 결과 실행 시간 메모리 Grader output
1 Correct 1751 ms 5984 KB Output is correct
2 Correct 1740 ms 6136 KB Output is correct
3 Correct 1746 ms 6008 KB Output is correct
4 Correct 1779 ms 6116 KB Output is correct
5 Correct 1741 ms 6136 KB Output is correct
6 Correct 1762 ms 6264 KB Output is correct
7 Correct 1744 ms 6576 KB Output is correct
8 Correct 1761 ms 6512 KB Output is correct
9 Correct 1752 ms 6588 KB Output is correct
10 Correct 1752 ms 6484 KB Output is correct
11 Correct 1762 ms 6504 KB Output is correct
12 Correct 1752 ms 6444 KB Output is correct
13 Correct 1749 ms 6264 KB Output is correct
14 Correct 1753 ms 6520 KB Output is correct
15 Correct 1754 ms 6364 KB Output is correct
16 Incorrect 309 ms 4600 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1751 ms 5984 KB Output is correct
2 Correct 1740 ms 6136 KB Output is correct
3 Correct 1746 ms 6008 KB Output is correct
4 Correct 1779 ms 6116 KB Output is correct
5 Correct 1741 ms 6136 KB Output is correct
6 Correct 1762 ms 6264 KB Output is correct
7 Correct 1744 ms 6576 KB Output is correct
8 Correct 1761 ms 6512 KB Output is correct
9 Correct 1752 ms 6588 KB Output is correct
10 Correct 1752 ms 6484 KB Output is correct
11 Correct 1762 ms 6504 KB Output is correct
12 Correct 1752 ms 6444 KB Output is correct
13 Correct 1749 ms 6264 KB Output is correct
14 Correct 1753 ms 6520 KB Output is correct
15 Correct 1754 ms 6364 KB Output is correct
16 Incorrect 309 ms 4600 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 1664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1751 ms 5984 KB Output is correct
2 Correct 1740 ms 6136 KB Output is correct
3 Correct 1746 ms 6008 KB Output is correct
4 Correct 1779 ms 6116 KB Output is correct
5 Correct 1741 ms 6136 KB Output is correct
6 Correct 1762 ms 6264 KB Output is correct
7 Correct 1744 ms 6576 KB Output is correct
8 Correct 1761 ms 6512 KB Output is correct
9 Correct 1752 ms 6588 KB Output is correct
10 Correct 1752 ms 6484 KB Output is correct
11 Correct 1762 ms 6504 KB Output is correct
12 Correct 1752 ms 6444 KB Output is correct
13 Correct 1749 ms 6264 KB Output is correct
14 Correct 1753 ms 6520 KB Output is correct
15 Correct 1754 ms 6364 KB Output is correct
16 Incorrect 309 ms 4600 KB Output isn't correct
17 Halted 0 ms 0 KB -