oj.uz

Submission #404873

# Submission time Handle Problem Language Result Execution time Memory
404873 2021-05-15T08:02:40 Z Forested Boat (APIO16_boat) C++17
9 / 100
 311 ms 9268 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 + 1, vector<Mint>(n + 1));
    rep(i, k) {
        int d = ps[i + 1] - ps[i];
        rep(j, min(d, n) + 1) {
            rep(k, j + 1) {
                _sum[i][j] += comb[i][k] * comb2[j][k];
            }
        }
    }
    
    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[j - 1][cnt - 1]) * 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

# Verdict Execution time Memory Grader output
1 Correct 298 ms 9268 KB Output is correct
2 Correct 308 ms 9148 KB Output is correct
3 Correct 304 ms 9228 KB Output is correct
4 Correct 300 ms 9144 KB Output is correct
5 Correct 301 ms 9216 KB Output is correct
6 Correct 303 ms 9148 KB Output is correct
7 Correct 311 ms 9156 KB Output is correct
8 Correct 297 ms 9228 KB Output is correct
9 Correct 299 ms 9156 KB Output is correct
10 Correct 301 ms 9232 KB Output is correct
11 Correct 307 ms 9156 KB Output is correct
12 Correct 303 ms 9232 KB Output is correct
13 Correct 301 ms 9144 KB Output is correct
14 Correct 310 ms 9228 KB Output is correct
15 Correct 302 ms 9148 KB Output is correct
16 Correct 56 ms 2628 KB Output is correct
17 Correct 62 ms 2848 KB Output is correct
18 Correct 56 ms 2692 KB Output is correct
19 Correct 59 ms 2756 KB Output is correct
20 Correct 57 ms 2688 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 9268 KB Output is correct
2 Correct 308 ms 9148 KB Output is correct
3 Correct 304 ms 9228 KB Output is correct
4 Correct 300 ms 9144 KB Output is correct
5 Correct 301 ms 9216 KB Output is correct
6 Correct 303 ms 9148 KB Output is correct
7 Correct 311 ms 9156 KB Output is correct
8 Correct 297 ms 9228 KB Output is correct
9 Correct 299 ms 9156 KB Output is correct
10 Correct 301 ms 9232 KB Output is correct
11 Correct 307 ms 9156 KB Output is correct
12 Correct 303 ms 9232 KB Output is correct
13 Correct 301 ms 9144 KB Output is correct
14 Correct 310 ms 9228 KB Output is correct
15 Correct 302 ms 9148 KB Output is correct
16 Correct 56 ms 2628 KB Output is correct
17 Correct 62 ms 2848 KB Output is correct
18 Correct 56 ms 2692 KB Output is correct
19 Correct 59 ms 2756 KB Output is correct
20 Correct 57 ms 2688 KB Output is correct
21 Incorrect 34 ms 8580 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 9268 KB Output is correct
2 Correct 308 ms 9148 KB Output is correct
3 Correct 304 ms 9228 KB Output is correct
4 Correct 300 ms 9144 KB Output is correct
5 Correct 301 ms 9216 KB Output is correct
6 Correct 303 ms 9148 KB Output is correct
7 Correct 311 ms 9156 KB Output is correct
8 Correct 297 ms 9228 KB Output is correct
9 Correct 299 ms 9156 KB Output is correct
10 Correct 301 ms 9232 KB Output is correct
11 Correct 307 ms 9156 KB Output is correct
12 Correct 303 ms 9232 KB Output is correct
13 Correct 301 ms 9144 KB Output is correct
14 Correct 310 ms 9228 KB Output is correct
15 Correct 302 ms 9148 KB Output is correct
16 Correct 56 ms 2628 KB Output is correct
17 Correct 62 ms 2848 KB Output is correct
18 Correct 56 ms 2692 KB Output is correct
19 Correct 59 ms 2756 KB Output is correct
20 Correct 57 ms 2688 KB Output is correct
21 Incorrect 34 ms 8580 KB Output isn't correct
22 Halted 0 ms 0 KB -