oj.uz

Submission #152849

# Submission time Handle Problem Language Result Execution time Memory
152849 2019-09-10T06:31:56 Z arnold518 Boat (APIO16_boat) C++14
9 / 100
 1455 ms 11536 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]=mypow(i, MOD-2);

    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)%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 781 ms 11440 KB Output is correct
2 Correct 785 ms 11308 KB Output is correct
3 Correct 778 ms 11384 KB Output is correct
4 Correct 777 ms 11256 KB Output is correct
5 Correct 777 ms 11324 KB Output is correct
6 Correct 775 ms 11256 KB Output is correct
7 Correct 771 ms 11344 KB Output is correct
8 Correct 772 ms 11536 KB Output is correct
9 Correct 785 ms 11376 KB Output is correct
10 Correct 772 ms 11476 KB Output is correct
11 Correct 769 ms 11512 KB Output is correct
12 Correct 777 ms 11376 KB Output is correct
13 Correct 768 ms 11356 KB Output is correct
14 Correct 773 ms 11384 KB Output is correct
15 Correct 773 ms 11380 KB Output is correct
16 Correct 143 ms 9980 KB Output is correct
17 Correct 154 ms 10104 KB Output is correct
18 Correct 152 ms 9976 KB Output is correct
19 Correct 154 ms 10076 KB Output is correct
20 Correct 156 ms 10168 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 11440 KB Output is correct
2 Correct 785 ms 11308 KB Output is correct
3 Correct 778 ms 11384 KB Output is correct
4 Correct 777 ms 11256 KB Output is correct
5 Correct 777 ms 11324 KB Output is correct
6 Correct 775 ms 11256 KB Output is correct
7 Correct 771 ms 11344 KB Output is correct
8 Correct 772 ms 11536 KB Output is correct
9 Correct 785 ms 11376 KB Output is correct
10 Correct 772 ms 11476 KB Output is correct
11 Correct 769 ms 11512 KB Output is correct
12 Correct 777 ms 11376 KB Output is correct
13 Correct 768 ms 11356 KB Output is correct
14 Correct 773 ms 11384 KB Output is correct
15 Correct 773 ms 11380 KB Output is correct
16 Correct 143 ms 9980 KB Output is correct
17 Correct 154 ms 10104 KB Output is correct
18 Correct 152 ms 9976 KB Output is correct
19 Correct 154 ms 10076 KB Output is correct
20 Correct 156 ms 10168 KB Output is correct
21 Incorrect 1455 ms 11316 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 7800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 11440 KB Output is correct
2 Correct 785 ms 11308 KB Output is correct
3 Correct 778 ms 11384 KB Output is correct
4 Correct 777 ms 11256 KB Output is correct
5 Correct 777 ms 11324 KB Output is correct
6 Correct 775 ms 11256 KB Output is correct
7 Correct 771 ms 11344 KB Output is correct
8 Correct 772 ms 11536 KB Output is correct
9 Correct 785 ms 11376 KB Output is correct
10 Correct 772 ms 11476 KB Output is correct
11 Correct 769 ms 11512 KB Output is correct
12 Correct 777 ms 11376 KB Output is correct
13 Correct 768 ms 11356 KB Output is correct
14 Correct 773 ms 11384 KB Output is correct
15 Correct 773 ms 11380 KB Output is correct
16 Correct 143 ms 9980 KB Output is correct
17 Correct 154 ms 10104 KB Output is correct
18 Correct 152 ms 9976 KB Output is correct
19 Correct 154 ms 10076 KB Output is correct
20 Correct 156 ms 10168 KB Output is correct
21 Incorrect 1455 ms 11316 KB Output isn't correct
22 Halted 0 ms 0 KB -