oj.uz

Submission #459907

# Submission time Handle Problem Language Result Execution time Memory
459907 2021-08-09T03:08:36 Z izhang05 Skyscraper (JOI16_skyscraper) C++17
100 / 100
 130 ms 130480 KB 
#include <bits/stdc++.h>

using namespace std;

//#define DEBUG
void setIO(const string &name) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin.exceptions(istream::failbit);
#ifdef LOCAL
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
    freopen((name + ".out").c_str(), "w", stderr);
#endif
}

template<typename T>
T mod_inv_in_range(T a, T m) {
    // assert(0 <= a && a < m);
    T x = a, y = m;
    T vx = 1, vy = 0;
    while (x) {
        T k = y / x;
        y %= x;
        vy -= k * vx;
        std::swap(x, y);
        std::swap(vx, vy);
    }
    assert(y == 1);
    return vy < 0 ? m + vy : vy;
}

template<int MOD_>
struct modnum {
    static constexpr int MOD = MOD_;
    static_assert(MOD_ > 0, "MOD must be positive");

private:
    using ll = long long;

    int v;

public:
    modnum() : v(0) {}

    modnum(ll v_) : v(int(v_ % MOD)) {
        if (v < 0) v += MOD;
    }

    explicit operator int() const { return v; }

    friend std::ostream &operator<<(std::ostream &out, const modnum &n) { return out << int(n); }

    friend std::istream &operator>>(std::istream &in, modnum &n) {
        ll v_;
        in >> v_;
        n = modnum(v_);
        return in;
    }

    friend bool operator==(const modnum &a, const modnum &b) { return a.v == b.v; }

    friend bool operator!=(const modnum &a, const modnum &b) { return a.v != b.v; }

    modnum inv() const {
        modnum res;
        res.v = mod_inv_in_range(v, MOD);
        return res;
    }

    friend modnum inv(const modnum &m) { return m.inv(); }

    modnum neg() const {
        modnum res;
        res.v = v ? MOD - v : 0;
        return res;
    }

    friend modnum neg(const modnum &m) { return m.neg(); }

    modnum operator-() const {
        return neg();
    }

    modnum operator+() const {
        return modnum(*this);
    }

    modnum &operator++() {
        v++;
        if (v == MOD) v = 0;
        return *this;
    }

    modnum &operator--() {
        if (v == 0) v = MOD;
        v--;
        return *this;
    }

    modnum &operator+=(const modnum &o) {
        v -= MOD - o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }

    modnum &operator-=(const modnum &o) {
        v -= o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }

    modnum &operator*=(const modnum &o) {
        v = int(ll(v) * ll(o.v) % MOD);
        return *this;
    }

    modnum &operator/=(const modnum &o) {
        return *this *= o.inv();
    }

    friend modnum operator++(modnum &a, int) {
        modnum r = a;
        ++a;
        return r;
    }

    friend modnum operator--(modnum &a, int) {
        modnum r = a;
        --a;
        return r;
    }

    friend modnum operator+(const modnum &a, const modnum &b) { return modnum(a) += b; }

    friend modnum operator-(const modnum &a, const modnum &b) { return modnum(a) -= b; }

    friend modnum operator*(const modnum &a, const modnum &b) { return modnum(a) *= b; }

    friend modnum operator/(const modnum &a, const modnum &b) { return modnum(a) /= b; }
};

const int inf = 0x3f3f3f3f, mod = 1e9 + 7, maxn = 105, maxl = 1005;
const long long INFL = 0x3f3f3f3f3f3f3f3f;

modnum<mod> dp[maxn][maxn][maxl][3];
/*
dp[i][j][k][l] :
i - number of numbers placed
j - number of connected components
k - total sum currently (filling empty spaces with a_{i} (0-indexed)
l - number of endpoints that are filled
*/

int main() {
    setIO("1");

    int n, l;
    cin >> n >> l;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    if (n == 1) {
        cout << 1 << "\n";
        return 0;
    }
    sort(a.begin(), a.end());
    a.push_back(10000);
    if (a[1] - a[0] <= l) {
        dp[1][1][a[1] - a[0]][1] = 2; //fill a[0] at one of the endpoints, there are 2 endpoints to fill.
    }
    if (2 * (a[1] - a[0]) <= l) {
        dp[1][1][2 * (a[1] - a[0])][0] = 1; //fill a[0] in the middle, positions doesn't matter.
    }
    for (int i = 1; i < n; i++) {
        int diff = a[i + 1] - a[i]; //this thing is "INF" if i = n - 1.
        for (int j = 1; j <= i; j++) {
            for (int k = 0; k <= l; k++) {
                for (int z = 0; z < 3; z++) {
                    modnum<mod> cur = dp[i][j][k][z];
                    if (cur == 0) continue; //this value does not exist
                    //First, we try to fill one of the ends
                    int new_k = k + diff * (2 * j - z - 1); //there are 2*j - z - 1 positions that we're supposed to "upgrade" (-1 because one of the positions is merged with the endpoints after this move)
                    if (z < 2 && new_k <= l) {
                        if (i == n - 1) {
                            dp[i + 1][j][new_k][z + 1] += cur * (2 - z) * j; //we have j con. comp. to choose to merge with
                        } else if (z == 0 || j > 1)                          //otherwise this coincides with i == n - 1
                        {
                            dp[i + 1][j][new_k][z + 1] += cur * (2 - z) * (j - z); //can only merge with the con comp. that are not connected to ends.
                        }
                        if (k + diff * (2 * j - z + 1) <= l) //now we create a new cc.
                        {
                            dp[i + 1][j + 1][k + diff * (2 * j - z + 1)][z + 1] += cur * (2 - z); //we can choose one of the ends to create
                        }
                    }
                    //Next, we dont fill the ends.
                    //Part 1 : Create new cc
                    new_k = k + diff * (2 * j - z + 2);
                    if (new_k <= l) //2 new positions to "upgrade"
                    {
                        dp[i + 1][j + 1][new_k][z] += cur; //nothing new happens
                    }
                    //Part 2 : Stick to one cc
                    new_k = k + diff * (2 * j - z);
                    if (new_k <= l) //no new positions to "upgrade"
                    {
                        dp[i + 1][j][new_k][z] += cur * (2 * j - z); //we can merge in 2*j - z possible positions
                    }
                    //Part 3 : Merge two ccs together
                    new_k = k + diff * (2 * j - z - 2);
                    if ((new_k <= l) && (j >= 2) && (i == n - 1 || j > 2 || z < 2)) {
                        if (z == 0) {
                            dp[i + 1][j - 1][new_k][z] += cur * j * (j - 1); //there are jP2 possible merges
                        }
                        if (z == 1) {
                            dp[i + 1][j - 1][new_k][z] += cur * (j - 1) * (j - 1); //there are (j-1)P2+(j-1) merges
                        }
                        if (z == 2) {
                            if (i == n - 1) {
                                dp[i + 1][j - 1][new_k][z] += cur; //there's only 1 place it can go.
                            } else {
                                dp[i + 1][j - 1][new_k][z] += cur * (j - 2) * (j - 1); //there're (j-2)P2 + 2(j-2) possiblilities
                            }
                        }
                    }
                }
            }
        }
    }
    modnum<mod> answer = 0;
    for (int i = 0; i <= l; i++) {
        answer += dp[n][1][i][2]; //sum the dp values for all possible sums
    }
    cout << answer << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 130348 KB Output is correct
2 Correct 80 ms 130316 KB Output is correct
3 Correct 83 ms 130288 KB Output is correct
4 Correct 82 ms 130372 KB Output is correct
5 Correct 81 ms 130292 KB Output is correct
6 Correct 82 ms 130300 KB Output is correct
7 Correct 88 ms 130320 KB Output is correct
8 Correct 79 ms 130376 KB Output is correct
9 Correct 80 ms 130372 KB Output is correct
10 Correct 79 ms 130288 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 130296 KB Output is correct
2 Correct 82 ms 130356 KB Output is correct
3 Correct 79 ms 130380 KB Output is correct
4 Correct 79 ms 130372 KB Output is correct
5 Correct 77 ms 130304 KB Output is correct
6 Correct 90 ms 130284 KB Output is correct
7 Correct 79 ms 130352 KB Output is correct
8 Correct 80 ms 130376 KB Output is correct
9 Correct 79 ms 130328 KB Output is correct
10 Correct 80 ms 130392 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 130348 KB Output is correct
2 Correct 80 ms 130316 KB Output is correct
3 Correct 83 ms 130288 KB Output is correct
4 Correct 82 ms 130372 KB Output is correct
5 Correct 81 ms 130292 KB Output is correct
6 Correct 82 ms 130300 KB Output is correct
7 Correct 88 ms 130320 KB Output is correct
8 Correct 79 ms 130376 KB Output is correct
9 Correct 80 ms 130372 KB Output is correct
10 Correct 79 ms 130288 KB Output is correct
11 Correct 82 ms 130296 KB Output is correct
12 Correct 82 ms 130356 KB Output is correct
13 Correct 79 ms 130380 KB Output is correct
14 Correct 79 ms 130372 KB Output is correct
15 Correct 77 ms 130304 KB Output is correct
16 Correct 90 ms 130284 KB Output is correct
17 Correct 79 ms 130352 KB Output is correct
18 Correct 80 ms 130376 KB Output is correct
19 Correct 79 ms 130328 KB Output is correct
20 Correct 80 ms 130392 KB Output is correct
21 Correct 90 ms 130376 KB Output is correct
22 Correct 130 ms 130392 KB Output is correct
23 Correct 122 ms 130368 KB Output is correct
24 Correct 119 ms 130412 KB Output is correct
25 Correct 120 ms 130364 KB Output is correct
26 Correct 117 ms 130480 KB Output is correct
27 Correct 94 ms 130372 KB Output is correct
28 Correct 99 ms 130372 KB Output is correct
29 Correct 117 ms 130404 KB Output is correct
30 Correct 120 ms 130368 KB Output is correct