oj.uz

Submission #738774

# Submission time Handle Problem Language Result Execution time Memory
738774 2023-05-09T13:35:28 Z Jarif_Rahman Boat (APIO16_boat) C++17
9 / 100
 1659 ms 46880 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;

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

    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);
    }
    void init(){
        fac[0] = 1, facinv[0] = 1;
        for(int i = 1; i < n; i++) fac[i] = (fac[i-1]*i)%md;
        facinv[n-1] = pw(fac[n-1], md-2);
        for(int i = n-2; i >= 0; i--) facinv[i] = (facinv[i+1]*(i+1))%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;


    vector<vector<ll>> C(m, vector<ll>(n+1, 0));
    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++){
            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];
    };

    vector<vector<ll>> dp(n, vector<ll>(m, 0)), dp_sum = dp;

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 43396 KB Output is correct
2 Correct 940 ms 43396 KB Output is correct
3 Correct 882 ms 43396 KB Output is correct
4 Correct 921 ms 43400 KB Output is correct
5 Correct 859 ms 43396 KB Output is correct
6 Correct 928 ms 43400 KB Output is correct
7 Correct 948 ms 43388 KB Output is correct
8 Correct 923 ms 43396 KB Output is correct
9 Correct 904 ms 43392 KB Output is correct
10 Correct 935 ms 43396 KB Output is correct
11 Correct 933 ms 43396 KB Output is correct
12 Correct 988 ms 43392 KB Output is correct
13 Correct 1027 ms 43392 KB Output is correct
14 Correct 968 ms 43400 KB Output is correct
15 Correct 914 ms 43396 KB Output is correct
16 Correct 142 ms 33612 KB Output is correct
17 Correct 142 ms 33852 KB Output is correct
18 Correct 142 ms 33768 KB Output is correct
19 Correct 138 ms 33788 KB Output is correct
20 Correct 137 ms 33764 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 43396 KB Output is correct
2 Correct 940 ms 43396 KB Output is correct
3 Correct 882 ms 43396 KB Output is correct
4 Correct 921 ms 43400 KB Output is correct
5 Correct 859 ms 43396 KB Output is correct
6 Correct 928 ms 43400 KB Output is correct
7 Correct 948 ms 43388 KB Output is correct
8 Correct 923 ms 43396 KB Output is correct
9 Correct 904 ms 43392 KB Output is correct
10 Correct 935 ms 43396 KB Output is correct
11 Correct 933 ms 43396 KB Output is correct
12 Correct 988 ms 43392 KB Output is correct
13 Correct 1027 ms 43392 KB Output is correct
14 Correct 968 ms 43400 KB Output is correct
15 Correct 914 ms 43396 KB Output is correct
16 Correct 142 ms 33612 KB Output is correct
17 Correct 142 ms 33852 KB Output is correct
18 Correct 142 ms 33768 KB Output is correct
19 Correct 138 ms 33788 KB Output is correct
20 Correct 137 ms 33764 KB Output is correct
21 Incorrect 1659 ms 46880 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 43396 KB Output is correct
2 Correct 940 ms 43396 KB Output is correct
3 Correct 882 ms 43396 KB Output is correct
4 Correct 921 ms 43400 KB Output is correct
5 Correct 859 ms 43396 KB Output is correct
6 Correct 928 ms 43400 KB Output is correct
7 Correct 948 ms 43388 KB Output is correct
8 Correct 923 ms 43396 KB Output is correct
9 Correct 904 ms 43392 KB Output is correct
10 Correct 935 ms 43396 KB Output is correct
11 Correct 933 ms 43396 KB Output is correct
12 Correct 988 ms 43392 KB Output is correct
13 Correct 1027 ms 43392 KB Output is correct
14 Correct 968 ms 43400 KB Output is correct
15 Correct 914 ms 43396 KB Output is correct
16 Correct 142 ms 33612 KB Output is correct
17 Correct 142 ms 33852 KB Output is correct
18 Correct 142 ms 33768 KB Output is correct
19 Correct 138 ms 33788 KB Output is correct
20 Correct 137 ms 33764 KB Output is correct
21 Incorrect 1659 ms 46880 KB Output isn't correct
22 Halted 0 ms 0 KB -