oj.uz

Submission #738762

# Submission time Handle Problem Language Result Execution time Memory
738762 2023-05-09T13:31:35 Z Jarif_Rahman Boat (APIO16_boat) C++17
0 / 100
 495 ms 63984 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 == 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++) assert(ranges[i+1]-ranges[i] < 1.5e6);

    vector<vector<ll>> C(m, vector<ll>(n+1, 0));
    for(int i = 0; i < m; i++){
        int x = ranges[i+1]-ranges[i];
        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: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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 449 ms 63984 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 449 ms 63984 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 495 ms 63896 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 449 ms 63984 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -