Submission #459904

#	Time	Username	Problem	Language	Result	Execution time	Memory
459904		izhang05	Skyscraper (JOI16_skyscraper)	C++17	0 / 100	225 ms	264220 KiB

skyscraper

#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(inf);
    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: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 80