oj.uz

Submission #738888

# Submission time Handle Problem Language Result Execution time Memory
738888 2023-05-09T15:22:22 Z Jarif_Rahman Boat (APIO16_boat) C++17
36 / 100
 867 ms 18068 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(!nested(j, k)) c++;
                if(j == 0 && k) continue;
                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 597 ms 18068 KB Output is correct
2 Correct 643 ms 17976 KB Output is correct
3 Correct 667 ms 18060 KB Output is correct
4 Correct 661 ms 17940 KB Output is correct
5 Correct 649 ms 18008 KB Output is correct
6 Correct 642 ms 17944 KB Output is correct
7 Correct 640 ms 17996 KB Output is correct
8 Correct 616 ms 18036 KB Output is correct
9 Correct 654 ms 18000 KB Output is correct
10 Correct 690 ms 17968 KB Output is correct
11 Correct 657 ms 17976 KB Output is correct
12 Correct 656 ms 17916 KB Output is correct
13 Correct 769 ms 17964 KB Output is correct
14 Correct 657 ms 17992 KB Output is correct
15 Correct 679 ms 17992 KB Output is correct
16 Correct 223 ms 9076 KB Output is correct
17 Correct 249 ms 9240 KB Output is correct
18 Correct 213 ms 9176 KB Output is correct
19 Correct 214 ms 9312 KB Output is correct
20 Correct 234 ms 9100 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 18068 KB Output is correct
2 Correct 643 ms 17976 KB Output is correct
3 Correct 667 ms 18060 KB Output is correct
4 Correct 661 ms 17940 KB Output is correct
5 Correct 649 ms 18008 KB Output is correct
6 Correct 642 ms 17944 KB Output is correct
7 Correct 640 ms 17996 KB Output is correct
8 Correct 616 ms 18036 KB Output is correct
9 Correct 654 ms 18000 KB Output is correct
10 Correct 690 ms 17968 KB Output is correct
11 Correct 657 ms 17976 KB Output is correct
12 Correct 656 ms 17916 KB Output is correct
13 Correct 769 ms 17964 KB Output is correct
14 Correct 657 ms 17992 KB Output is correct
15 Correct 679 ms 17992 KB Output is correct
16 Correct 223 ms 9076 KB Output is correct
17 Correct 249 ms 9240 KB Output is correct
18 Correct 213 ms 9176 KB Output is correct
19 Correct 214 ms 9312 KB Output is correct
20 Correct 234 ms 9100 KB Output is correct
21 Incorrect 867 ms 18052 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4308 KB Output is correct
2 Correct 15 ms 4308 KB Output is correct
3 Correct 17 ms 4380 KB Output is correct
4 Correct 16 ms 4324 KB Output is correct
5 Correct 16 ms 4384 KB Output is correct
6 Correct 21 ms 4300 KB Output is correct
7 Correct 18 ms 4308 KB Output is correct
8 Correct 18 ms 4308 KB Output is correct
9 Correct 20 ms 4344 KB Output is correct
10 Correct 19 ms 4364 KB Output is correct
11 Correct 20 ms 4328 KB Output is correct
12 Correct 18 ms 4352 KB Output is correct
13 Correct 14 ms 4304 KB Output is correct
14 Correct 14 ms 4308 KB Output is correct
15 Correct 15 ms 4388 KB Output is correct
16 Correct 10 ms 2896 KB Output is correct
17 Correct 10 ms 2836 KB Output is correct
18 Correct 8 ms 2772 KB Output is correct
19 Correct 10 ms 2784 KB Output is correct
20 Correct 11 ms 2868 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 18068 KB Output is correct
2 Correct 643 ms 17976 KB Output is correct
3 Correct 667 ms 18060 KB Output is correct
4 Correct 661 ms 17940 KB Output is correct
5 Correct 649 ms 18008 KB Output is correct
6 Correct 642 ms 17944 KB Output is correct
7 Correct 640 ms 17996 KB Output is correct
8 Correct 616 ms 18036 KB Output is correct
9 Correct 654 ms 18000 KB Output is correct
10 Correct 690 ms 17968 KB Output is correct
11 Correct 657 ms 17976 KB Output is correct
12 Correct 656 ms 17916 KB Output is correct
13 Correct 769 ms 17964 KB Output is correct
14 Correct 657 ms 17992 KB Output is correct
15 Correct 679 ms 17992 KB Output is correct
16 Correct 223 ms 9076 KB Output is correct
17 Correct 249 ms 9240 KB Output is correct
18 Correct 213 ms 9176 KB Output is correct
19 Correct 214 ms 9312 KB Output is correct
20 Correct 234 ms 9100 KB Output is correct
21 Incorrect 867 ms 18052 KB Output isn't correct
22 Halted 0 ms 0 KB -