Submission #738774

#	Time	Username	Problem	Language	Result	Execution time	Memory
738774		Jarif_Rahman	Boat (APIO16_boat)	C++17	9 / 100	1659 ms	46880 KiB

boat

#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 (stderr)

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 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42