oj.uz

Submission #738798

# Submission time Handle Problem Language Result Execution time Memory
738798 2023-05-09T13:51:23 Z Jarif_Rahman Boat (APIO16_boat) C++17
9 / 100
 1718 ms 87940 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;
const int N = 500;
ll dp[N][2*N+1], dp_sum[N][2*N+1], C[2*N+1][N+1];

namespace combi{
    const int n = 2e6;
    ll fac[n], facinv[n];

    ll pw(ll x, ll p){
        if(p == 0) return 1;
        if(p%2 == 0) return pw((x*x)%md, p/2);
        return (pw(x, p-1)*x)%md;
    }
    void init(){
        fac[0] = 1, facinv[0] = 1;
        for(int i = 1; i < n; i++) fac[i] = (fac[i-1]*i)%md, facinv[i] = (facinv[i-1]*pw(i, md-2))%md;
    }
    ll nCr(int n, int r){
        if(r > n) return 0;
        ll rt = (fac[n]*facinv[r]);
        rt%=md;
        rt*=facinv[n-r];
        rt%=md;
        return rt;
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    combi::init();

    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 < m; i++){
        int x = ranges[i+1]-ranges[i];
        if(x > 1.5e6) continue;
        for(int j = 0; j <= n; j++){
            C[i][j] = 0;
            for(int k = 0; k <= j; k++)
                C[i][j]+=(combi::nCr(x, k+1)*combi::nCr(j, k))%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:54:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 |             for(int k = 0; k <= j; k++)
      |             ^~~
boat.cpp:56:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   56 |                 C[i][j]%=md;
      |                 ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1036 ms 43380 KB Output is correct
2 Correct 1079 ms 43344 KB Output is correct
3 Correct 1041 ms 43280 KB Output is correct
4 Correct 1053 ms 43404 KB Output is correct
5 Correct 1078 ms 43332 KB Output is correct
6 Correct 1071 ms 43340 KB Output is correct
7 Correct 1106 ms 43304 KB Output is correct
8 Correct 1112 ms 43380 KB Output is correct
9 Correct 1140 ms 43396 KB Output is correct
10 Correct 1168 ms 43348 KB Output is correct
11 Correct 1038 ms 43468 KB Output is correct
12 Correct 1095 ms 43268 KB Output is correct
13 Correct 1127 ms 43428 KB Output is correct
14 Correct 1118 ms 43400 KB Output is correct
15 Correct 1085 ms 43392 KB Output is correct
16 Correct 445 ms 37660 KB Output is correct
17 Correct 448 ms 37836 KB Output is correct
18 Correct 447 ms 37708 KB Output is correct
19 Correct 450 ms 37852 KB Output is correct
20 Correct 457 ms 37692 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1036 ms 43380 KB Output is correct
2 Correct 1079 ms 43344 KB Output is correct
3 Correct 1041 ms 43280 KB Output is correct
4 Correct 1053 ms 43404 KB Output is correct
5 Correct 1078 ms 43332 KB Output is correct
6 Correct 1071 ms 43340 KB Output is correct
7 Correct 1106 ms 43304 KB Output is correct
8 Correct 1112 ms 43380 KB Output is correct
9 Correct 1140 ms 43396 KB Output is correct
10 Correct 1168 ms 43348 KB Output is correct
11 Correct 1038 ms 43468 KB Output is correct
12 Correct 1095 ms 43268 KB Output is correct
13 Correct 1127 ms 43428 KB Output is correct
14 Correct 1118 ms 43400 KB Output is correct
15 Correct 1085 ms 43392 KB Output is correct
16 Correct 445 ms 37660 KB Output is correct
17 Correct 448 ms 37836 KB Output is correct
18 Correct 447 ms 37708 KB Output is correct
19 Correct 450 ms 37852 KB Output is correct
20 Correct 457 ms 37692 KB Output is correct
21 Runtime error 1718 ms 87940 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1036 ms 43380 KB Output is correct
2 Correct 1079 ms 43344 KB Output is correct
3 Correct 1041 ms 43280 KB Output is correct
4 Correct 1053 ms 43404 KB Output is correct
5 Correct 1078 ms 43332 KB Output is correct
6 Correct 1071 ms 43340 KB Output is correct
7 Correct 1106 ms 43304 KB Output is correct
8 Correct 1112 ms 43380 KB Output is correct
9 Correct 1140 ms 43396 KB Output is correct
10 Correct 1168 ms 43348 KB Output is correct
11 Correct 1038 ms 43468 KB Output is correct
12 Correct 1095 ms 43268 KB Output is correct
13 Correct 1127 ms 43428 KB Output is correct
14 Correct 1118 ms 43400 KB Output is correct
15 Correct 1085 ms 43392 KB Output is correct
16 Correct 445 ms 37660 KB Output is correct
17 Correct 448 ms 37836 KB Output is correct
18 Correct 447 ms 37708 KB Output is correct
19 Correct 450 ms 37852 KB Output is correct
20 Correct 457 ms 37692 KB Output is correct
21 Runtime error 1718 ms 87940 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -