oj.uz

답안 #310008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310008 2020-10-05T10:18:30 Z vipghn2003 Boat (APIO16_boat) C++14
27 / 100
 2000 ms 2552 KB 
#include<bits/stdc++.h>
#define int long long
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][N*2];

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

void init()
{
    gt[0]=1;
    for(int i=1;i<=N-5;i++) gt[i]=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]=igt[i+1]*(i+1)%mod;
}

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

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++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=j;k++) ways[i][j]=(ways[i][j]+C(k,val[i+1]-val[i])*C(k-1,j-1)%mod)%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]+sum[k-1][j-1]*ways[j][i-k+1-cnt]%mod)%mod;
                //if(i==2&&j==2) cout<<k<<' '<<i-k+1-cnt<<' '<<sum[k-1][j-1]*ways[j][i-k+1-cnt]%mod<<'\n';
            }
        }
        for(int j=1;j<=sz-1;j++)
        {
            sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
            //cout<<i<<' '<<val[j]<<' '<<val[j+1]<<' '<<dp[i][j]<<'\n';
        }
        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 Execution timed out 2078 ms 760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2078 ms 760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 344 ms 2296 KB Output is correct
2 Correct 338 ms 2424 KB Output is correct
3 Correct 345 ms 2388 KB Output is correct
4 Correct 343 ms 2300 KB Output is correct
5 Correct 339 ms 2352 KB Output is correct
6 Correct 340 ms 2552 KB Output is correct
7 Correct 340 ms 2552 KB Output is correct
8 Correct 342 ms 2424 KB Output is correct
9 Correct 337 ms 2524 KB Output is correct
10 Correct 339 ms 2424 KB Output is correct
11 Correct 338 ms 2424 KB Output is correct
12 Correct 339 ms 2424 KB Output is correct
13 Correct 336 ms 2424 KB Output is correct
14 Correct 342 ms 2424 KB Output is correct
15 Correct 336 ms 2424 KB Output is correct
16 Correct 173 ms 1912 KB Output is correct
17 Correct 168 ms 2040 KB Output is correct
18 Correct 172 ms 1784 KB Output is correct
19 Correct 171 ms 1868 KB Output is correct
20 Correct 171 ms 1784 KB Output is correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2078 ms 760 KB Time limit exceeded
2 Halted 0 ms 0 KB -