oj.uz

Submission #738826

# Submission time Handle Problem Language Result Execution time Memory
738826 2023-05-09T14:12:43 Z Jarif_Rahman Boat (APIO16_boat) C++17
9 / 100
 773 ms 18124 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll md = 1e9+7;
ll pw(ll x, ll p){
    if(!p) return 1;
    if(p&1) return (pw(x, p-1)*x)%md;
    return pw((x*x)%md, p>>1);
}

const int N = 500;
ll fac[N+5], facinv[N+5];
ll combiA[N+5][N+5], combiB[2*N+1][N+5];
ll dp[N][2*N+1], dp_sum[N][2*N+1], C[2*N+1][N+1];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    fac[0] = 1, facinv[0] = 1;
    for(int i = 1; i < N+5; i++) fac[i] = (fac[i-1]*i)%md, facinv[i] = (facinv[i-1]*pw(i, md-2))%md;

    int n; cin >> n;
    vector<int> L(n), R(n);
    vector<int> ranges, _ranges;
    for(int i = 0; i < n; i++) cin >> L[i] >> R[i], _ranges.pb(L[i]), _ranges.pb(R[i]), _ranges.pb(R[i]+1);
    sort(_ranges.begin(), _ranges.end());
    for(int x: _ranges)
        if(ranges.empty() || ranges.back() != x) ranges.pb(x);
    int m = int(ranges.size())-1;

    for(int i = 0; i <= n; i++) for(int j = 0; j <= i; j++){
        combiA[i][j] = facinv[j];
        for(int k = i-j+1; k <= i; k++) combiA[i][j]*=k, combiA[i][j]%=md;
    }
    for(int i = 0; i < m; i++){
        int x = ranges[i+1]-ranges[i];
        for(int j = 0; j <= n+1; j++){
            if(j > x){
                combiB[i][j] = 0;
                continue;
            }
            combiB[i][j] = facinv[j];
            for(int k = x-j+1; k <= x; k++) combiB[i][j]*=k, combiB[i][j]%=md;
        }
    }

    for(int i = 0; i < m; i++){
        for(int j = 0; j <= n; j++){
            C[i][j] = 0;
            for(int k = 0; k <= j; k++)
                C[i][j]+=(combiA[j][k]*combiB[i][k+1])%md;
                C[i][j]%=md;
        }
    }

    auto nested = [&](int j, int i){
        return ranges[j] >= L[i] && ranges[j+1]-1 <= R[i];
    };

    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) dp[i][j] = 0, dp_sum[i][j] = 0;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!nested(j, i)) continue;
            int c = 0;
            for(int k = i; k >= 0; k--){
                if(j == 0 && k) continue;
                if(!nested(j, k)) c++;
                dp[i][j]+=(C[j][i-k-c]*(k ? dp_sum[k-1][j-1]:1))%md;
                dp[i][j]%=md;
            }
        }
        for(int j = 0; j < m; j++){
            if(j) dp_sum[i][j] = dp_sum[i][j-1];
            dp_sum[i][j]+=dp[i][j];
            dp_sum[i][j]%=md;
        }
    }

    ll ans = 0;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) ans+=dp[i][j], ans%=md;
    cout << ans << "\n";
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:56:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   56 |             for(int k = 0; k <= j; k++)
      |             ^~~
boat.cpp:58:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |                 C[i][j]%=md;
      |                 ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 17980 KB Output is correct
2 Correct 687 ms 18124 KB Output is correct
3 Correct 638 ms 18044 KB Output is correct
4 Correct 716 ms 18008 KB Output is correct
5 Correct 773 ms 18008 KB Output is correct
6 Correct 675 ms 17984 KB Output is correct
7 Correct 615 ms 18008 KB Output is correct
8 Correct 625 ms 18120 KB Output is correct
9 Correct 596 ms 17996 KB Output is correct
10 Correct 599 ms 18048 KB Output is correct
11 Correct 583 ms 18024 KB Output is correct
12 Correct 602 ms 18008 KB Output is correct
13 Correct 603 ms 18000 KB Output is correct
14 Correct 608 ms 18008 KB Output is correct
15 Correct 574 ms 18020 KB Output is correct
16 Correct 191 ms 9084 KB Output is correct
17 Correct 186 ms 9276 KB Output is correct
18 Correct 187 ms 9124 KB Output is correct
19 Correct 186 ms 9184 KB Output is correct
20 Correct 187 ms 9180 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 17980 KB Output is correct
2 Correct 687 ms 18124 KB Output is correct
3 Correct 638 ms 18044 KB Output is correct
4 Correct 716 ms 18008 KB Output is correct
5 Correct 773 ms 18008 KB Output is correct
6 Correct 675 ms 17984 KB Output is correct
7 Correct 615 ms 18008 KB Output is correct
8 Correct 625 ms 18120 KB Output is correct
9 Correct 596 ms 17996 KB Output is correct
10 Correct 599 ms 18048 KB Output is correct
11 Correct 583 ms 18024 KB Output is correct
12 Correct 602 ms 18008 KB Output is correct
13 Correct 603 ms 18000 KB Output is correct
14 Correct 608 ms 18008 KB Output is correct
15 Correct 574 ms 18020 KB Output is correct
16 Correct 191 ms 9084 KB Output is correct
17 Correct 186 ms 9276 KB Output is correct
18 Correct 187 ms 9124 KB Output is correct
19 Correct 186 ms 9184 KB Output is correct
20 Correct 187 ms 9180 KB Output is correct
21 Incorrect 726 ms 18040 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 17980 KB Output is correct
2 Correct 687 ms 18124 KB Output is correct
3 Correct 638 ms 18044 KB Output is correct
4 Correct 716 ms 18008 KB Output is correct
5 Correct 773 ms 18008 KB Output is correct
6 Correct 675 ms 17984 KB Output is correct
7 Correct 615 ms 18008 KB Output is correct
8 Correct 625 ms 18120 KB Output is correct
9 Correct 596 ms 17996 KB Output is correct
10 Correct 599 ms 18048 KB Output is correct
11 Correct 583 ms 18024 KB Output is correct
12 Correct 602 ms 18008 KB Output is correct
13 Correct 603 ms 18000 KB Output is correct
14 Correct 608 ms 18008 KB Output is correct
15 Correct 574 ms 18020 KB Output is correct
16 Correct 191 ms 9084 KB Output is correct
17 Correct 186 ms 9276 KB Output is correct
18 Correct 187 ms 9124 KB Output is correct
19 Correct 186 ms 9184 KB Output is correct
20 Correct 187 ms 9180 KB Output is correct
21 Incorrect 726 ms 18040 KB Output isn't correct
22 Halted 0 ms 0 KB -