oj.uz

답안 #404884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404884 2021-05-15T08:37:35 Z Forested Boat (APIO16_boat) C++17
36 / 100
 573 ms 9216 KB 
// Template
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <tuple>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <array>
#include <cassert>
#include <cmath>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll infll = 3003003003003003003LL;
template <typename T>
inline bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T> 
inline bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &element : vec) is >> element;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    for (int i = 0, vec_len = (int)vec.size(); i < vec_len; ++i) {
        os << vec[i] << (i + 1 == vec_len ? "" : " ");
    }
    return os;
}
struct IOSET {
    IOSET() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} ioset;

// Mod-Int
#include <iostream>

template <unsigned int mod>
struct ModInt {
    static_assert(mod >= 1 && mod < (1u << 31));
    
    unsigned int val;
    
    ModInt() : val(0) {}
    
    ModInt(long long x) : val(x < 0 ? x % mod + mod : (unsigned long long)x % mod) {}
    
    ModInt<mod> &operator+=(const ModInt<mod> &x) {
        val += x.val;
        if (val >= mod) val -= mod;
        return *this;
    }
    
    ModInt<mod> &operator-=(const ModInt<mod> &x) {
        if (val < x.val) val += mod;
        val -= x.val;
        return *this;
    }
    
    ModInt<mod> &operator*=(const ModInt<mod> &x) {
        unsigned long long s = (unsigned long long)val * x.val;
        val = (unsigned int)(s % mod);
        return *this;
    }
    
    ModInt<mod> operator+() const {
        return *this;
    }
    
    ModInt<mod> operator-() const {
        return ModInt<mod>(0u) - *this;
    }
    
    friend ModInt<mod> operator+(const ModInt<mod> &x, const ModInt<mod> &y) {
        return ModInt<mod>(x) += y;
    }
    
    friend ModInt<mod> operator-(const ModInt<mod> &x, const ModInt<mod> &y) {
        return ModInt<mod>(x) -= y;
    }
    
    friend ModInt<mod> operator*(const ModInt<mod> &x, const ModInt<mod> &y) {
        return ModInt<mod>(x) *= y;
    }
    
    friend std::istream &operator>>(std::istream &is, ModInt<mod> &x) {
        is >> x.val;
        // x.value %= mod;
        return is;
    }
    
    friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &x) {
        os << x.val;
        return os;
    }
    
    ModInt<mod> pow(unsigned long long x) const {
        ModInt<mod> res(1), s(*this);
        while (x) {
            if (x & 1) res *= s;
            s *= s;
            x >>= 1;
        }
        return res;
    }
    
    // --- prime number ---
    ModInt<mod> &operator/=(const ModInt<mod> &x) {
        *this *= x.pow(mod - 2);
        return *this;
    }
    
    friend ModInt<mod> operator/(const ModInt<mod> &x, const ModInt<mod> &y) {
        return ModInt<mod>(x) /= y;
    }
};

// Main
int main() {
    constexpr unsigned mod = 1000000007;
    using Mint = ModInt<mod>;
    
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    rep(i, n) {
        cin >> a[i] >> b[i];
        ++b[i];
    }
    
    vector<int> ps;
    ps.reserve(2 * n);
    rep(i, n) {
        ps.push_back(a[i]);
        ps.push_back(b[i]);
    }
    sort(all(ps));
    ps.erase(unique(all(ps)), ps.end());
    rep(i, n) {
        a[i] = lower_bound(all(ps), a[i]) - ps.begin();
        b[i] = lower_bound(all(ps), b[i]) - ps.begin();
    }
    
    int k = ps.size() - 1;
    
    vector<vector<Mint>> comb(k, vector<Mint>(n + 1));
    rep(i, k) {
        int d = ps[i + 1] - ps[i];
        Mint p(1);
        comb[i][0] = Mint(1);
        rep(j, 1, min(d, n) + 1) {
            p *= Mint(d - j + 1);
            p /= Mint(j);
            comb[i][j] = p;
        }
    }
    vector<vector<Mint>> comb2(n + 1, vector<Mint>(n + 1));
    comb2[0][0] = Mint(1);
    rep(i, 1, n + 1) rep(j, i + 1) {
        comb2[i][j] += comb2[i - 1][j];
        if (j != 0) comb2[i][j] += comb2[i - 1][j - 1];
    }
    vector<vector<Mint>> _sum(k, vector<Mint>(n + 1));
    rep(i, k) {
        int d = ps[i + 1] - ps[i];
        _sum[i][1] = Mint(d);
        rep(j, 2, min(d, n) + 1) {
            rep(l, 2, j + 1) {
                _sum[i][j] += comb[i][l] * comb2[j][l] - Mint(2) * comb[i][l] * comb2[j - 1][l] + comb[i][l] * comb2[j - 2][l];
            }
        }
    }
    
    vector<vector<Mint>> dp(n + 1, vector<Mint>(k + 1)), sum(n + 1, vector<Mint>(k + 1));
    dp[0][0] = Mint(1);
    sum[0] = vector<Mint>(k + 1, Mint(1));
    rep(i, n) {
        dp[i + 1] = dp[i];
        sum[i + 1][0] = dp[i + 1][0];
        rep(j, 1, k + 1) {
            int d = ps[j] - ps[j - 1];
            int cnt = 0;
            for (int l = i; l >= 0; --l) {
                if (b[l] <= j - 1 || a[l] >= j) {
                    if (l == i) break;
                    continue;
                }
                if (++cnt > d) break;
                dp[i + 1][j] += _sum[j - 1][cnt] * sum[l][j - 1];
            }
            sum[i + 1][j] = sum[i + 1][j - 1] + dp[i + 1][j];
        }
    }
    
    cout << sum[n][k] - Mint(1) << '\n';
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 533 ms 9128 KB Output is correct
2 Correct 530 ms 9132 KB Output is correct
3 Correct 516 ms 9208 KB Output is correct
4 Correct 573 ms 9132 KB Output is correct
5 Correct 526 ms 9128 KB Output is correct
6 Correct 523 ms 9128 KB Output is correct
7 Correct 524 ms 9216 KB Output is correct
8 Correct 532 ms 9132 KB Output is correct
9 Correct 525 ms 9132 KB Output is correct
10 Correct 528 ms 9132 KB Output is correct
11 Correct 523 ms 9132 KB Output is correct
12 Correct 520 ms 9128 KB Output is correct
13 Correct 517 ms 9156 KB Output is correct
14 Correct 526 ms 9124 KB Output is correct
15 Correct 516 ms 9128 KB Output is correct
16 Correct 92 ms 2628 KB Output is correct
17 Correct 102 ms 2832 KB Output is correct
18 Correct 95 ms 2672 KB Output is correct
19 Correct 101 ms 2888 KB Output is correct
20 Correct 95 ms 2684 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 533 ms 9128 KB Output is correct
2 Correct 530 ms 9132 KB Output is correct
3 Correct 516 ms 9208 KB Output is correct
4 Correct 573 ms 9132 KB Output is correct
5 Correct 526 ms 9128 KB Output is correct
6 Correct 523 ms 9128 KB Output is correct
7 Correct 524 ms 9216 KB Output is correct
8 Correct 532 ms 9132 KB Output is correct
9 Correct 525 ms 9132 KB Output is correct
10 Correct 528 ms 9132 KB Output is correct
11 Correct 523 ms 9132 KB Output is correct
12 Correct 520 ms 9128 KB Output is correct
13 Correct 517 ms 9156 KB Output is correct
14 Correct 526 ms 9124 KB Output is correct
15 Correct 516 ms 9128 KB Output is correct
16 Correct 92 ms 2628 KB Output is correct
17 Correct 102 ms 2832 KB Output is correct
18 Correct 95 ms 2672 KB Output is correct
19 Correct 101 ms 2888 KB Output is correct
20 Correct 95 ms 2684 KB Output is correct
21 Incorrect 29 ms 8560 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 588 KB Output is correct
2 Correct 14 ms 656 KB Output is correct
3 Correct 16 ms 664 KB Output is correct
4 Correct 17 ms 588 KB Output is correct
5 Correct 15 ms 588 KB Output is correct
6 Correct 17 ms 588 KB Output is correct
7 Correct 18 ms 704 KB Output is correct
8 Correct 16 ms 588 KB Output is correct
9 Correct 16 ms 588 KB Output is correct
10 Correct 16 ms 696 KB Output is correct
11 Correct 14 ms 588 KB Output is correct
12 Correct 13 ms 696 KB Output is correct
13 Correct 16 ms 588 KB Output is correct
14 Correct 15 ms 660 KB Output is correct
15 Correct 16 ms 656 KB Output is correct
16 Correct 7 ms 460 KB Output is correct
17 Correct 7 ms 460 KB Output is correct
18 Correct 7 ms 460 KB Output is correct
19 Correct 7 ms 460 KB Output is correct
20 Correct 7 ms 460 KB Output is correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 533 ms 9128 KB Output is correct
2 Correct 530 ms 9132 KB Output is correct
3 Correct 516 ms 9208 KB Output is correct
4 Correct 573 ms 9132 KB Output is correct
5 Correct 526 ms 9128 KB Output is correct
6 Correct 523 ms 9128 KB Output is correct
7 Correct 524 ms 9216 KB Output is correct
8 Correct 532 ms 9132 KB Output is correct
9 Correct 525 ms 9132 KB Output is correct
10 Correct 528 ms 9132 KB Output is correct
11 Correct 523 ms 9132 KB Output is correct
12 Correct 520 ms 9128 KB Output is correct
13 Correct 517 ms 9156 KB Output is correct
14 Correct 526 ms 9124 KB Output is correct
15 Correct 516 ms 9128 KB Output is correct
16 Correct 92 ms 2628 KB Output is correct
17 Correct 102 ms 2832 KB Output is correct
18 Correct 95 ms 2672 KB Output is correct
19 Correct 101 ms 2888 KB Output is correct
20 Correct 95 ms 2684 KB Output is correct
21 Incorrect 29 ms 8560 KB Output isn't correct
22 Halted 0 ms 0 KB -