oj.uz

답안 #404880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404880 2021-05-15T08:35:06 Z Forested Boat (APIO16_boat) C++17
36 / 100
 568 ms 9340 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, 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 563 ms 9252 KB Output is correct
2 Correct 525 ms 9136 KB Output is correct
3 Correct 567 ms 9132 KB Output is correct
4 Correct 534 ms 9132 KB Output is correct
5 Correct 529 ms 9340 KB Output is correct
6 Correct 519 ms 9124 KB Output is correct
7 Correct 526 ms 9156 KB Output is correct
8 Correct 534 ms 9132 KB Output is correct
9 Correct 568 ms 9252 KB Output is correct
10 Correct 527 ms 9128 KB Output is correct
11 Correct 560 ms 9156 KB Output is correct
12 Correct 530 ms 9136 KB Output is correct
13 Correct 527 ms 9156 KB Output is correct
14 Correct 532 ms 9132 KB Output is correct
15 Correct 519 ms 9132 KB Output is correct
16 Correct 95 ms 2648 KB Output is correct
17 Correct 104 ms 2828 KB Output is correct
18 Correct 98 ms 2724 KB Output is correct
19 Correct 110 ms 2824 KB Output is correct
20 Correct 103 ms 2672 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 563 ms 9252 KB Output is correct
2 Correct 525 ms 9136 KB Output is correct
3 Correct 567 ms 9132 KB Output is correct
4 Correct 534 ms 9132 KB Output is correct
5 Correct 529 ms 9340 KB Output is correct
6 Correct 519 ms 9124 KB Output is correct
7 Correct 526 ms 9156 KB Output is correct
8 Correct 534 ms 9132 KB Output is correct
9 Correct 568 ms 9252 KB Output is correct
10 Correct 527 ms 9128 KB Output is correct
11 Correct 560 ms 9156 KB Output is correct
12 Correct 530 ms 9136 KB Output is correct
13 Correct 527 ms 9156 KB Output is correct
14 Correct 532 ms 9132 KB Output is correct
15 Correct 519 ms 9132 KB Output is correct
16 Correct 95 ms 2648 KB Output is correct
17 Correct 104 ms 2828 KB Output is correct
18 Correct 98 ms 2724 KB Output is correct
19 Correct 110 ms 2824 KB Output is correct
20 Correct 103 ms 2672 KB Output is correct
21 Incorrect 29 ms 8584 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 656 KB Output is correct
2 Correct 14 ms 660 KB Output is correct
3 Correct 15 ms 588 KB Output is correct
4 Correct 15 ms 704 KB Output is correct
5 Correct 15 ms 700 KB Output is correct
6 Correct 16 ms 704 KB Output is correct
7 Correct 16 ms 700 KB Output is correct
8 Correct 17 ms 664 KB Output is correct
9 Correct 16 ms 588 KB Output is correct
10 Correct 16 ms 700 KB Output is correct
11 Correct 16 ms 656 KB Output is correct
12 Correct 14 ms 660 KB Output is correct
13 Correct 14 ms 656 KB Output is correct
14 Correct 14 ms 664 KB Output is correct
15 Correct 17 ms 588 KB Output is correct
16 Correct 7 ms 448 KB Output is correct
17 Correct 7 ms 440 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 563 ms 9252 KB Output is correct
2 Correct 525 ms 9136 KB Output is correct
3 Correct 567 ms 9132 KB Output is correct
4 Correct 534 ms 9132 KB Output is correct
5 Correct 529 ms 9340 KB Output is correct
6 Correct 519 ms 9124 KB Output is correct
7 Correct 526 ms 9156 KB Output is correct
8 Correct 534 ms 9132 KB Output is correct
9 Correct 568 ms 9252 KB Output is correct
10 Correct 527 ms 9128 KB Output is correct
11 Correct 560 ms 9156 KB Output is correct
12 Correct 530 ms 9136 KB Output is correct
13 Correct 527 ms 9156 KB Output is correct
14 Correct 532 ms 9132 KB Output is correct
15 Correct 519 ms 9132 KB Output is correct
16 Correct 95 ms 2648 KB Output is correct
17 Correct 104 ms 2828 KB Output is correct
18 Correct 98 ms 2724 KB Output is correct
19 Correct 110 ms 2824 KB Output is correct
20 Correct 103 ms 2672 KB Output is correct
21 Incorrect 29 ms 8584 KB Output isn't correct
22 Halted 0 ms 0 KB -