Submission #738892

#	Time	Username	Problem	Language	Result	Execution time	Memory
738892		Jarif_Rahman	Boat (APIO16_boat)	C++17	100 / 100	1375 ms	18240 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;
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]+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 (stderr)

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