oj.uz

Submission #679650

# Submission time Handle Problem Language Result Execution time Memory
679650 2023-01-08T20:04:47 Z bebra Boat (APIO16_boat) C++17
36 / 100
 363 ms 4008 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

int add(int a, int b) {
    int res = a + b;
    if (res >= MOD) res -= MOD;
    return res;
}

int mul(long long a, int b) {
    return a * b % MOD;
}

int binpow(int base, int power) {
    int res = 1;
    while (power > 0) {
        if (power & 1) {
            res = mul(res, base);
        }
        base = mul(base, base);
        power >>= 1;
    }
    return res;
}

const int MAX_N = 600;
int dp[MAX_N][2 * MAX_N];
int c[MAX_N][MAX_N];

int a[MAX_N];
int b[MAX_N];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> p;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        p.push_back(a[i]);
        p.push_back(b[i] + 1);
    }
    sort(p.begin(), p.end());
    p.resize(unique(p.begin(), p.end()) - p.begin());
    vector<pair<int, int>> segments;
    for (int i = 0; i < (int)p.size() - 1; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[j] <= p[i] && p[i + 1] - 1 <= b[j]) {
                segments.emplace_back(p[i], p[i + 1] - 1);
                break;
            }
        }
    }
    int m = segments.size();
    segments.insert(segments.begin(), {-1, -1});
    for (int i = 1; i <= m; ++i) {
        auto [l, r] = segments[i];
        c[i][1] = r - l + 1;
        for (int j = 2; j <= n; ++j) {
            c[i][j] = mul(c[i][j - 1], mul(r - l + j, binpow(j, MOD - 2)));
        }
    }
    for (int j = 0; j <= m; ++j) {
        dp[0][j] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = 1;
        for (int j = 1; j <= m; ++j) {
            auto [l, r] = segments[j];
            dp[i][j] = dp[i][j - 1];
            int cnt = 0;
            for (int k = i; k >= 1; --k) {
                if (a[k] <= l && r <= b[k]) {
                    ++cnt;
                    dp[i][j] = add(dp[i][j], mul(dp[k - 1][j - 1], c[j][cnt]));
                }
            }
        }
    }
    cout << dp[n][m] - 1 << '\n';
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 3840 KB Output is correct
2 Correct 182 ms 3832 KB Output is correct
3 Correct 190 ms 3852 KB Output is correct
4 Correct 185 ms 3800 KB Output is correct
5 Correct 184 ms 3772 KB Output is correct
6 Correct 125 ms 3808 KB Output is correct
7 Correct 123 ms 3768 KB Output is correct
8 Correct 130 ms 3772 KB Output is correct
9 Correct 125 ms 3864 KB Output is correct
10 Correct 127 ms 3792 KB Output is correct
11 Correct 124 ms 3792 KB Output is correct
12 Correct 128 ms 3756 KB Output is correct
13 Correct 121 ms 3780 KB Output is correct
14 Correct 122 ms 3760 KB Output is correct
15 Correct 122 ms 3760 KB Output is correct
16 Correct 38 ms 2636 KB Output is correct
17 Correct 41 ms 2700 KB Output is correct
18 Correct 39 ms 2644 KB Output is correct
19 Correct 40 ms 2596 KB Output is correct
20 Correct 40 ms 2644 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 3840 KB Output is correct
2 Correct 182 ms 3832 KB Output is correct
3 Correct 190 ms 3852 KB Output is correct
4 Correct 185 ms 3800 KB Output is correct
5 Correct 184 ms 3772 KB Output is correct
6 Correct 125 ms 3808 KB Output is correct
7 Correct 123 ms 3768 KB Output is correct
8 Correct 130 ms 3772 KB Output is correct
9 Correct 125 ms 3864 KB Output is correct
10 Correct 127 ms 3792 KB Output is correct
11 Correct 124 ms 3792 KB Output is correct
12 Correct 128 ms 3756 KB Output is correct
13 Correct 121 ms 3780 KB Output is correct
14 Correct 122 ms 3760 KB Output is correct
15 Correct 122 ms 3760 KB Output is correct
16 Correct 38 ms 2636 KB Output is correct
17 Correct 41 ms 2700 KB Output is correct
18 Correct 39 ms 2644 KB Output is correct
19 Correct 40 ms 2596 KB Output is correct
20 Correct 40 ms 2644 KB Output is correct
21 Incorrect 363 ms 4008 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 6 ms 1236 KB Output is correct
3 Correct 7 ms 1236 KB Output is correct
4 Correct 7 ms 1236 KB Output is correct
5 Correct 7 ms 1236 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 7 ms 1236 KB Output is correct
8 Correct 7 ms 1228 KB Output is correct
9 Correct 8 ms 1236 KB Output is correct
10 Correct 7 ms 1216 KB Output is correct
11 Correct 7 ms 1236 KB Output is correct
12 Correct 7 ms 1236 KB Output is correct
13 Correct 7 ms 1236 KB Output is correct
14 Correct 7 ms 1236 KB Output is correct
15 Correct 6 ms 1236 KB Output is correct
16 Correct 4 ms 980 KB Output is correct
17 Correct 4 ms 980 KB Output is correct
18 Correct 5 ms 980 KB Output is correct
19 Correct 4 ms 980 KB Output is correct
20 Correct 4 ms 992 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 3840 KB Output is correct
2 Correct 182 ms 3832 KB Output is correct
3 Correct 190 ms 3852 KB Output is correct
4 Correct 185 ms 3800 KB Output is correct
5 Correct 184 ms 3772 KB Output is correct
6 Correct 125 ms 3808 KB Output is correct
7 Correct 123 ms 3768 KB Output is correct
8 Correct 130 ms 3772 KB Output is correct
9 Correct 125 ms 3864 KB Output is correct
10 Correct 127 ms 3792 KB Output is correct
11 Correct 124 ms 3792 KB Output is correct
12 Correct 128 ms 3756 KB Output is correct
13 Correct 121 ms 3780 KB Output is correct
14 Correct 122 ms 3760 KB Output is correct
15 Correct 122 ms 3760 KB Output is correct
16 Correct 38 ms 2636 KB Output is correct
17 Correct 41 ms 2700 KB Output is correct
18 Correct 39 ms 2644 KB Output is correct
19 Correct 40 ms 2596 KB Output is correct
20 Correct 40 ms 2644 KB Output is correct
21 Incorrect 363 ms 4008 KB Output isn't correct
22 Halted 0 ms 0 KB -