oj.uz

Submission #738770

# Submission time Handle Problem Language Result Execution time Memory
738770 2023-05-09T13:33:31 Z Jarif_Rahman Boat (APIO16_boat) C++17
9 / 100
 2000 ms 46980 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;


    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: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 1289 ms 43380 KB Output is correct
2 Correct 1169 ms 43408 KB Output is correct
3 Correct 1235 ms 43468 KB Output is correct
4 Correct 1160 ms 43528 KB Output is correct
5 Correct 1278 ms 43404 KB Output is correct
6 Correct 1188 ms 43412 KB Output is correct
7 Correct 1193 ms 43424 KB Output is correct
8 Correct 1287 ms 43428 KB Output is correct
9 Correct 1315 ms 43408 KB Output is correct
10 Correct 1209 ms 43340 KB Output is correct
11 Correct 1194 ms 43400 KB Output is correct
12 Correct 1151 ms 43424 KB Output is correct
13 Correct 1175 ms 43512 KB Output is correct
14 Correct 1193 ms 43412 KB Output is correct
15 Correct 1212 ms 43408 KB Output is correct
16 Correct 475 ms 33704 KB Output is correct
17 Correct 504 ms 33828 KB Output is correct
18 Correct 486 ms 33772 KB Output is correct
19 Correct 500 ms 33800 KB Output is correct
20 Correct 468 ms 33868 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1289 ms 43380 KB Output is correct
2 Correct 1169 ms 43408 KB Output is correct
3 Correct 1235 ms 43468 KB Output is correct
4 Correct 1160 ms 43528 KB Output is correct
5 Correct 1278 ms 43404 KB Output is correct
6 Correct 1188 ms 43412 KB Output is correct
7 Correct 1193 ms 43424 KB Output is correct
8 Correct 1287 ms 43428 KB Output is correct
9 Correct 1315 ms 43408 KB Output is correct
10 Correct 1209 ms 43340 KB Output is correct
11 Correct 1194 ms 43400 KB Output is correct
12 Correct 1151 ms 43424 KB Output is correct
13 Correct 1175 ms 43512 KB Output is correct
14 Correct 1193 ms 43412 KB Output is correct
15 Correct 1212 ms 43408 KB Output is correct
16 Correct 475 ms 33704 KB Output is correct
17 Correct 504 ms 33828 KB Output is correct
18 Correct 486 ms 33772 KB Output is correct
19 Correct 500 ms 33800 KB Output is correct
20 Correct 468 ms 33868 KB Output is correct
21 Execution timed out 2003 ms 46980 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1289 ms 43380 KB Output is correct
2 Correct 1169 ms 43408 KB Output is correct
3 Correct 1235 ms 43468 KB Output is correct
4 Correct 1160 ms 43528 KB Output is correct
5 Correct 1278 ms 43404 KB Output is correct
6 Correct 1188 ms 43412 KB Output is correct
7 Correct 1193 ms 43424 KB Output is correct
8 Correct 1287 ms 43428 KB Output is correct
9 Correct 1315 ms 43408 KB Output is correct
10 Correct 1209 ms 43340 KB Output is correct
11 Correct 1194 ms 43400 KB Output is correct
12 Correct 1151 ms 43424 KB Output is correct
13 Correct 1175 ms 43512 KB Output is correct
14 Correct 1193 ms 43412 KB Output is correct
15 Correct 1212 ms 43408 KB Output is correct
16 Correct 475 ms 33704 KB Output is correct
17 Correct 504 ms 33828 KB Output is correct
18 Correct 486 ms 33772 KB Output is correct
19 Correct 500 ms 33800 KB Output is correct
20 Correct 468 ms 33868 KB Output is correct
21 Execution timed out 2003 ms 46980 KB Time limit exceeded
22 Halted 0 ms 0 KB -