oj.uz

Submission #738814

# Submission time Handle Problem Language Result Execution time Memory
738814 2023-05-09T14:06:12 Z Jarif_Rahman Boat (APIO16_boat) C++17
9 / 100
 1710 ms 18104 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;
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]), _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++){
            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(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:52:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   52 |             for(int k = 0; k <= j; k++)
      |             ^~~
boat.cpp:54:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   54 |                 C[i][j]%=md;
      |                 ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 18012 KB Output is correct
2 Correct 855 ms 18072 KB Output is correct
3 Correct 871 ms 18052 KB Output is correct
4 Correct 882 ms 17988 KB Output is correct
5 Correct 878 ms 18036 KB Output is correct
6 Correct 860 ms 17916 KB Output is correct
7 Correct 863 ms 18004 KB Output is correct
8 Correct 861 ms 18092 KB Output is correct
9 Correct 886 ms 18028 KB Output is correct
10 Correct 873 ms 18024 KB Output is correct
11 Correct 881 ms 17924 KB Output is correct
12 Correct 883 ms 18032 KB Output is correct
13 Correct 909 ms 17968 KB Output is correct
14 Correct 901 ms 18104 KB Output is correct
15 Correct 913 ms 17996 KB Output is correct
16 Correct 268 ms 9028 KB Output is correct
17 Correct 270 ms 9256 KB Output is correct
18 Correct 283 ms 9164 KB Output is correct
19 Correct 297 ms 9248 KB Output is correct
20 Correct 276 ms 9220 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 18012 KB Output is correct
2 Correct 855 ms 18072 KB Output is correct
3 Correct 871 ms 18052 KB Output is correct
4 Correct 882 ms 17988 KB Output is correct
5 Correct 878 ms 18036 KB Output is correct
6 Correct 860 ms 17916 KB Output is correct
7 Correct 863 ms 18004 KB Output is correct
8 Correct 861 ms 18092 KB Output is correct
9 Correct 886 ms 18028 KB Output is correct
10 Correct 873 ms 18024 KB Output is correct
11 Correct 881 ms 17924 KB Output is correct
12 Correct 883 ms 18032 KB Output is correct
13 Correct 909 ms 17968 KB Output is correct
14 Correct 901 ms 18104 KB Output is correct
15 Correct 913 ms 17996 KB Output is correct
16 Correct 268 ms 9028 KB Output is correct
17 Correct 270 ms 9256 KB Output is correct
18 Correct 283 ms 9164 KB Output is correct
19 Correct 297 ms 9248 KB Output is correct
20 Correct 276 ms 9220 KB Output is correct
21 Incorrect 1710 ms 17964 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 18012 KB Output is correct
2 Correct 855 ms 18072 KB Output is correct
3 Correct 871 ms 18052 KB Output is correct
4 Correct 882 ms 17988 KB Output is correct
5 Correct 878 ms 18036 KB Output is correct
6 Correct 860 ms 17916 KB Output is correct
7 Correct 863 ms 18004 KB Output is correct
8 Correct 861 ms 18092 KB Output is correct
9 Correct 886 ms 18028 KB Output is correct
10 Correct 873 ms 18024 KB Output is correct
11 Correct 881 ms 17924 KB Output is correct
12 Correct 883 ms 18032 KB Output is correct
13 Correct 909 ms 17968 KB Output is correct
14 Correct 901 ms 18104 KB Output is correct
15 Correct 913 ms 17996 KB Output is correct
16 Correct 268 ms 9028 KB Output is correct
17 Correct 270 ms 9256 KB Output is correct
18 Correct 283 ms 9164 KB Output is correct
19 Correct 297 ms 9248 KB Output is correct
20 Correct 276 ms 9220 KB Output is correct
21 Incorrect 1710 ms 17964 KB Output isn't correct
22 Halted 0 ms 0 KB -