oj.uz

Submission #310009

# Submission time Handle Problem Language Result Execution time Memory
310009 2020-10-05T10:20:27 Z vipghn2003 Boat (APIO16_boat) C++14
27 / 100
 2000 ms 2428 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;
    if(n<=500) gt[n]*igt[n-k]%mod*igt[k]%mod;
    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: In function 'long long int C(long long int, long long int)':
boat.cpp:28:41: warning: statement has no effect [-Wunused-value]
   28 |     if(n<=500) gt[n]*igt[n-k]%mod*igt[k]%mod;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
boat.cpp: At global scope:
boat.cpp:34:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main()
      |      ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 2304 KB Output is correct
2 Correct 339 ms 2424 KB Output is correct
3 Correct 340 ms 2424 KB Output is correct
4 Correct 339 ms 2424 KB Output is correct
5 Correct 341 ms 2424 KB Output is correct
6 Correct 342 ms 2296 KB Output is correct
7 Correct 340 ms 2424 KB Output is correct
8 Correct 342 ms 2424 KB Output is correct
9 Correct 338 ms 2424 KB Output is correct
10 Correct 338 ms 2428 KB Output is correct
11 Correct 337 ms 2296 KB Output is correct
12 Correct 337 ms 2424 KB Output is correct
13 Correct 343 ms 2424 KB Output is correct
14 Correct 338 ms 2296 KB Output is correct
15 Correct 336 ms 2340 KB Output is correct
16 Correct 173 ms 1912 KB Output is correct
17 Correct 174 ms 1836 KB Output is correct
18 Correct 171 ms 1916 KB Output is correct
19 Correct 170 ms 1784 KB Output is correct
20 Correct 170 ms 1784 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 760 KB Time limit exceeded
2 Halted 0 ms 0 KB -