oj.uz

Submission #681621

# Submission time Handle Problem Language Result Execution time Memory
681621 2023-01-13T13:12:20 Z 79brue Boat (APIO16_boat) C++17
9 / 100
 744 ms 18544 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

ll mpow(ll x, ll y){
    if(!y) return 1;
    if(y%2) return mpow(x, y-1) * x % MOD;
    ll tmp = mpow(x, y/2);
    return tmp * tmp % MOD;
}

ll modInv(ll x){
    return mpow(x, MOD-2);
}

int n, k;
ll a[502], b[502];
ll arr[1002];

void input();
void init();
void solve();
void output();

int main(){
    input();
    init();
    solve();
    output();
}

void input(){
    vector<int> vec;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &a[i], &b[i]);
        a[i]--;
        vec.push_back(a[i]);
        vec.push_back(b[i]);
    }
    vec.push_back(0);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    k = (int)vec.size() - 1;
    for(int i=0; i<=k; i++) arr[i] = vec[i];

    for(int i=1; i<=n; i++){
        a[i] = lower_bound(arr, arr+k+1, a[i]) - arr + 1;
        b[i] = lower_bound(arr, arr+k+1, b[i]) - arr;
    }
}

ll nCk[502][502];
ll xCi[1002][502];
ll xySum[1002][502];

void init(){
    /// nCk
    for(int i=0; i<=n; i++){
        nCk[i][0] = nCk[i][i] = 1;
        for(int j=1; j<i; j++){
            nCk[i][j] = (nCk[i-1][j] + nCk[i-1][j-1]) % MOD;
        }
    }

    /// xCi
    for(int i=1; i<=k; i++){
        ll X = arr[i] - arr[i-1];
        xCi[i][1] = X;
        for(int j=2; j<=n; j++){
            xCi[i][j] = xCi[i][j] * (X-j+1) % MOD * modInv(j) % MOD;
        }
    }

    /// xyMult
    for(int i=1; i<=k; i++){
        for(int j=1; j<=n; j++){
            for(int d=1; d<=j; d++){
                xySum[i][j] = (xySum[i][j] + xCi[i][d] * nCk[j-1][d-1]) % MOD;
            }
        }
    }
}

int sum[502][1002];
ll DP[502][1002];
ll DPsum[502][1002];

void solve(){
    /// sum
    for(int i=1; i<=n; i++){
        for(int j=a[i]; j<=b[i]; j++){
            sum[i][j] = 1;
        }
    }
    for(int j=1; j<=k; j++) for(int i=1; i<=n; i++) sum[i][j] += sum[i-1][j];

    DP[0][0] = 1;
    for(int i=0; i<=k; i++) DPsum[0][i] = 1;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            if(j < a[i] || b[i] < j) continue;
            for(int prv=0; prv<i; prv++){
                DP[i][j] = (DP[i][j] + DPsum[prv][j-1] * xySum[j][sum[i][j]-sum[prv][j]]) % MOD;
            }
        }

        for(int j=1; j<=k; j++) DPsum[i][j] = (DPsum[i][j-1] + DP[i][j]) % MOD;

//        for(int j=1; j<=k; j++) printf("%lld ", DP[i][j]);
//        puts("");
    }
}

ll ans;

void output(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            ans = (ans + DP[i][j]) % MOD;
        }
    }

    printf("%lld", ans);
}

Compilation message

boat.cpp: In function 'void input()':
boat.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
boat.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%lld %lld", &a[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 18024 KB Output is correct
2 Correct 635 ms 18136 KB Output is correct
3 Correct 619 ms 18124 KB Output is correct
4 Correct 618 ms 17928 KB Output is correct
5 Correct 619 ms 18096 KB Output is correct
6 Correct 618 ms 18080 KB Output is correct
7 Correct 616 ms 18124 KB Output is correct
8 Correct 618 ms 17952 KB Output is correct
9 Correct 621 ms 18044 KB Output is correct
10 Correct 619 ms 18128 KB Output is correct
11 Correct 628 ms 18008 KB Output is correct
12 Correct 616 ms 18024 KB Output is correct
13 Correct 619 ms 18044 KB Output is correct
14 Correct 611 ms 18124 KB Output is correct
15 Correct 614 ms 18092 KB Output is correct
16 Correct 112 ms 10312 KB Output is correct
17 Correct 122 ms 10504 KB Output is correct
18 Correct 122 ms 10328 KB Output is correct
19 Correct 121 ms 10500 KB Output is correct
20 Correct 119 ms 10332 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 18024 KB Output is correct
2 Correct 635 ms 18136 KB Output is correct
3 Correct 619 ms 18124 KB Output is correct
4 Correct 618 ms 17928 KB Output is correct
5 Correct 619 ms 18096 KB Output is correct
6 Correct 618 ms 18080 KB Output is correct
7 Correct 616 ms 18124 KB Output is correct
8 Correct 618 ms 17952 KB Output is correct
9 Correct 621 ms 18044 KB Output is correct
10 Correct 619 ms 18128 KB Output is correct
11 Correct 628 ms 18008 KB Output is correct
12 Correct 616 ms 18024 KB Output is correct
13 Correct 619 ms 18044 KB Output is correct
14 Correct 611 ms 18124 KB Output is correct
15 Correct 614 ms 18092 KB Output is correct
16 Correct 112 ms 10312 KB Output is correct
17 Correct 122 ms 10504 KB Output is correct
18 Correct 122 ms 10328 KB Output is correct
19 Correct 121 ms 10500 KB Output is correct
20 Correct 119 ms 10332 KB Output is correct
21 Incorrect 744 ms 18544 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 18024 KB Output is correct
2 Correct 635 ms 18136 KB Output is correct
3 Correct 619 ms 18124 KB Output is correct
4 Correct 618 ms 17928 KB Output is correct
5 Correct 619 ms 18096 KB Output is correct
6 Correct 618 ms 18080 KB Output is correct
7 Correct 616 ms 18124 KB Output is correct
8 Correct 618 ms 17952 KB Output is correct
9 Correct 621 ms 18044 KB Output is correct
10 Correct 619 ms 18128 KB Output is correct
11 Correct 628 ms 18008 KB Output is correct
12 Correct 616 ms 18024 KB Output is correct
13 Correct 619 ms 18044 KB Output is correct
14 Correct 611 ms 18124 KB Output is correct
15 Correct 614 ms 18092 KB Output is correct
16 Correct 112 ms 10312 KB Output is correct
17 Correct 122 ms 10504 KB Output is correct
18 Correct 122 ms 10328 KB Output is correct
19 Correct 121 ms 10500 KB Output is correct
20 Correct 119 ms 10332 KB Output is correct
21 Incorrect 744 ms 18544 KB Output isn't correct
22 Halted 0 ms 0 KB -