oj.uz

Submission #152848

# Submission time Handle Problem Language Result Execution time Memory
152848 2019-09-10T06:28:41 Z arnold518 Boat (APIO16_boat) C++14
9 / 100
 1448 ms 11520 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1000;
const ll MOD = 1e9+7;

int N, S, A[MAXN+10], B[MAXN+10];
vector<int> comp;

ll inv[MAXN+10], dp[MAXN+10][MAXN+10], bino[MAXN+10][MAXN+10], comb[MAXN+10], f[MAXN+10], ans;

int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin(); }

ll mypow(ll x, ll y)
{
    if(y==0) return 1;
    if(y%2) return mypow(x, y-1)*x%MOD;
    ll t=mypow(x, y/2);
    return t*t%MOD;
}

int main()
{
    int i, j, k;
    bino[0][0]=1;
    for(i=1; i<=MAXN; i++) for(j=0; j<=i; j++)
    {
        if(j==0 || j==i) bino[i][j]=1;
        else bino[i][j]=(bino[i-1][j]+bino[i-1][j-1])%MOD;
    }

    inv[0]=1;
    for(i=1; i<=MAXN; i++) inv[i]=inv[i-1]*mypow(i, MOD-2)%MOD;

    scanf("%d", &N);
    for(i=1; i<=N; i++)
    {
        scanf("%d%d", &A[i], &B[i]);
        B[i]++;
        comp.push_back(A[i]);
        comp.push_back(B[i]);
    }
    comp.push_back(0);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    S=comp.size()-1;

    for(i=0; i<S; i++) dp[0][i]=1;
    for(i=1; i<=N; i++) dp[i][0]=1;
    for(i=1; i<S; i++)
    {
        memset(comb, 0, sizeof(comb));
        memset(f, 0, sizeof(f));

        ll sz=comp[i+1]-comp[i]; comb[0]=1;
        for(j=1; j<=N; j++) comb[j]=comb[j-1]*(sz+1-j)%MOD*inv[j]%MOD;
        for(j=1; j<=N; j++) for(k=1; k<=j; k++) f[j]=(f[j]+comb[k]*bino[j-1][k-1])%MOD;

        for(j=1; j<=N; j++)
        {
            if(getcomp(A[j])<=i && i<getcomp(B[j]))
            {
                int cnt=1;
                for(k=1; k<=j; k++)
                {
                    if(i==1) dp[j][i]=f[cnt]%MOD;
                    else
                    {
                        dp[j][i]+=dp[j-k][i-1]*f[cnt]%MOD;
                        dp[j][i]%=MOD;
                    }
                    if((getcomp(A[j-k]<=i && i<getcomp(B[j-k])))) cnt++;
                }
            }
            if(i>1) dp[j][i]+=dp[j][i-1], dp[j][i]%=MOD;
        }
    }
    for(i=1; i<=N; i++) ans=(ans+dp[i][S-1])%MOD;
    printf("%lld", ans);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
boat.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &A[i], &B[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 755 ms 11428 KB Output is correct
2 Correct 752 ms 11344 KB Output is correct
3 Correct 772 ms 11384 KB Output is correct
4 Correct 752 ms 11396 KB Output is correct
5 Correct 750 ms 11456 KB Output is correct
6 Correct 743 ms 11256 KB Output is correct
7 Correct 744 ms 11388 KB Output is correct
8 Correct 759 ms 11316 KB Output is correct
9 Correct 753 ms 11408 KB Output is correct
10 Correct 745 ms 11452 KB Output is correct
11 Correct 744 ms 11384 KB Output is correct
12 Correct 758 ms 11328 KB Output is correct
13 Correct 746 ms 11328 KB Output is correct
14 Correct 744 ms 11388 KB Output is correct
15 Correct 770 ms 11520 KB Output is correct
16 Correct 138 ms 9976 KB Output is correct
17 Correct 152 ms 10180 KB Output is correct
18 Correct 143 ms 10224 KB Output is correct
19 Correct 149 ms 10272 KB Output is correct
20 Correct 144 ms 9976 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 755 ms 11428 KB Output is correct
2 Correct 752 ms 11344 KB Output is correct
3 Correct 772 ms 11384 KB Output is correct
4 Correct 752 ms 11396 KB Output is correct
5 Correct 750 ms 11456 KB Output is correct
6 Correct 743 ms 11256 KB Output is correct
7 Correct 744 ms 11388 KB Output is correct
8 Correct 759 ms 11316 KB Output is correct
9 Correct 753 ms 11408 KB Output is correct
10 Correct 745 ms 11452 KB Output is correct
11 Correct 744 ms 11384 KB Output is correct
12 Correct 758 ms 11328 KB Output is correct
13 Correct 746 ms 11328 KB Output is correct
14 Correct 744 ms 11388 KB Output is correct
15 Correct 770 ms 11520 KB Output is correct
16 Correct 138 ms 9976 KB Output is correct
17 Correct 152 ms 10180 KB Output is correct
18 Correct 143 ms 10224 KB Output is correct
19 Correct 149 ms 10272 KB Output is correct
20 Correct 144 ms 9976 KB Output is correct
21 Incorrect 1448 ms 11444 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 755 ms 11428 KB Output is correct
2 Correct 752 ms 11344 KB Output is correct
3 Correct 772 ms 11384 KB Output is correct
4 Correct 752 ms 11396 KB Output is correct
5 Correct 750 ms 11456 KB Output is correct
6 Correct 743 ms 11256 KB Output is correct
7 Correct 744 ms 11388 KB Output is correct
8 Correct 759 ms 11316 KB Output is correct
9 Correct 753 ms 11408 KB Output is correct
10 Correct 745 ms 11452 KB Output is correct
11 Correct 744 ms 11384 KB Output is correct
12 Correct 758 ms 11328 KB Output is correct
13 Correct 746 ms 11328 KB Output is correct
14 Correct 744 ms 11388 KB Output is correct
15 Correct 770 ms 11520 KB Output is correct
16 Correct 138 ms 9976 KB Output is correct
17 Correct 152 ms 10180 KB Output is correct
18 Correct 143 ms 10224 KB Output is correct
19 Correct 149 ms 10272 KB Output is correct
20 Correct 144 ms 9976 KB Output is correct
21 Incorrect 1448 ms 11444 KB Output isn't correct
22 Halted 0 ms 0 KB -