oj.uz

Submission #376463

# Submission time Handle Problem Language Result Execution time Memory
376463 2021-03-11T13:57:15 Z KoD Boat (APIO16_boat) C++17
9 / 100
 706 ms 6704 KB 
#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

constexpr int MOD = 1000000007;

struct Fp {
    int val;
    Fp(const int val = 0): val(((val % MOD) + MOD) % MOD) { }
    Fp& operator += (const Fp &other) {
        if ((val += other.val) >= MOD) val -= MOD;
        return *this;
    }
    Fp operator + (const Fp &other) const {
        return Fp(*this) += other;
    }
    Fp& operator -= (const Fp &other) {
        if ((val += MOD - other.val) >= MOD) val -= MOD;
        return *this;
    }
    Fp operator - (const Fp &other) const {
        return Fp(*this) -= other;
    }
    Fp& operator *= (const Fp &other) {
        val = (long long) val * other.val % MOD;
        return *this;
    }
    Fp operator * (const Fp &other) const {
        return Fp(*this) *= other;
    }
    Fp& operator /= (const Fp &other) {
        return *this *= other.inv();
    }
    Fp operator / (const Fp &other) const {
        return Fp(*this) /= other;
    }
    Fp inv() const {
        return pow(MOD - 2);
    }
    Fp pow(int e) const {
        Fp ret(1), mult(*this);
        while (e > 1) {
            if (e & 1) ret *= mult;
            mult *= mult;
            e >>= 1;
        }
        return ret;
    }
};

int main() {
    int N;
    std::cin >> N;
    Vec<int> A(N), B(N);
    Vec<int> cmp;
    cmp.reserve(2 * N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i] >> B[i];
        B[i] += 1;
        cmp.push_back(A[i]);
        cmp.push_back(B[i]);
    }
    std::sort(cmp.begin(), cmp.end());
    cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
    for (auto &x: A) {
        x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
    }
    for (auto &x: B) {
        x = std::lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin();
    }
    const auto size = (int) cmp.size() - 1;
    Vec<Vec<Fp>> coeff(size, Vec<Fp>(N + 1));
    for (int k = 0; k < size; ++k) {
        Fp val(cmp[k + 1] - cmp[k]);
        for (int j = 1; j <= N; ++j) {
            if (cmp[k + 1] - cmp[k] < j) {
                break;
            }
            coeff[k][j] = val;
            val *= Fp(cmp[k + 1] - cmp[k] - j);
            val /= Fp(j + 1);
        }
    }
    Vec<Vec<Fp>> dp(size, Vec<Fp>(N + 1));
    for (int k = 0; k < size; ++k) {
        dp[k][0] = Fp(1);
    }
    Fp ans;
    for (int i = 0; i < N; ++i) {
        Vec<Vec<Fp>> next(size, Vec<Fp>(N + 1));
        Fp sum;
        for (int k = 0; k < size; ++k) {
            next[k][0] += sum;
            for (int j = 0; j <= N; ++j) {
                if (dp[k][j].val == 0) {
                    continue;
                }
                next[k][j] += dp[k][j];
                if (A[i] <= k && k < B[i]) {
                    next[k][j + 1] += dp[k][j];
                    const auto end = dp[k][j] * coeff[k][j + 1];
                    ans += end;
                    sum += end;
                }
            }
        }
        dp = std::move(next);
    }
    std::cout << ans.val << '\n';
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 6552 KB Output is correct
2 Correct 671 ms 6704 KB Output is correct
3 Correct 670 ms 6424 KB Output is correct
4 Correct 689 ms 6696 KB Output is correct
5 Correct 691 ms 6496 KB Output is correct
6 Correct 685 ms 6492 KB Output is correct
7 Correct 680 ms 6432 KB Output is correct
8 Correct 676 ms 6436 KB Output is correct
9 Correct 675 ms 6504 KB Output is correct
10 Correct 668 ms 6416 KB Output is correct
11 Correct 679 ms 6584 KB Output is correct
12 Correct 683 ms 6528 KB Output is correct
13 Correct 690 ms 6440 KB Output is correct
14 Correct 683 ms 6536 KB Output is correct
15 Correct 684 ms 6536 KB Output is correct
16 Correct 107 ms 1436 KB Output is correct
17 Correct 114 ms 1516 KB Output is correct
18 Correct 110 ms 1468 KB Output is correct
19 Correct 115 ms 1644 KB Output is correct
20 Correct 111 ms 1484 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 6552 KB Output is correct
2 Correct 671 ms 6704 KB Output is correct
3 Correct 670 ms 6424 KB Output is correct
4 Correct 689 ms 6696 KB Output is correct
5 Correct 691 ms 6496 KB Output is correct
6 Correct 685 ms 6492 KB Output is correct
7 Correct 680 ms 6432 KB Output is correct
8 Correct 676 ms 6436 KB Output is correct
9 Correct 675 ms 6504 KB Output is correct
10 Correct 668 ms 6416 KB Output is correct
11 Correct 679 ms 6584 KB Output is correct
12 Correct 683 ms 6528 KB Output is correct
13 Correct 690 ms 6440 KB Output is correct
14 Correct 683 ms 6536 KB Output is correct
15 Correct 684 ms 6536 KB Output is correct
16 Correct 107 ms 1436 KB Output is correct
17 Correct 114 ms 1516 KB Output is correct
18 Correct 110 ms 1468 KB Output is correct
19 Correct 115 ms 1644 KB Output is correct
20 Correct 111 ms 1484 KB Output is correct
21 Incorrect 706 ms 5976 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 6552 KB Output is correct
2 Correct 671 ms 6704 KB Output is correct
3 Correct 670 ms 6424 KB Output is correct
4 Correct 689 ms 6696 KB Output is correct
5 Correct 691 ms 6496 KB Output is correct
6 Correct 685 ms 6492 KB Output is correct
7 Correct 680 ms 6432 KB Output is correct
8 Correct 676 ms 6436 KB Output is correct
9 Correct 675 ms 6504 KB Output is correct
10 Correct 668 ms 6416 KB Output is correct
11 Correct 679 ms 6584 KB Output is correct
12 Correct 683 ms 6528 KB Output is correct
13 Correct 690 ms 6440 KB Output is correct
14 Correct 683 ms 6536 KB Output is correct
15 Correct 684 ms 6536 KB Output is correct
16 Correct 107 ms 1436 KB Output is correct
17 Correct 114 ms 1516 KB Output is correct
18 Correct 110 ms 1468 KB Output is correct
19 Correct 115 ms 1644 KB Output is correct
20 Correct 111 ms 1484 KB Output is correct
21 Incorrect 706 ms 5976 KB Output isn't correct
22 Halted 0 ms 0 KB -