Submission #404234

#	Time	Username	Problem	Language	Result	Execution time	Memory
404234		timmyfeng	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	140 ms	120316 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

const int N = 101, L = 1001, M = 1000000007;

struct mint {
    int x;

    mint() : x(0) {}

    template <class T> mint(T value) : x(value % M) { if (x < 0) x += M; }

    mint & operator+=(const mint &oth) { x += oth.x; if (x >= M) x -= M; return *this; }

    mint & operator-=(const mint &oth) { x -= oth.x; if (x < 0) x += M; return *this; }

    mint & operator*=(const mint &oth) { x = (long long) x * oth.x % M; return *this; }

    friend mint operator+(mint l, const mint &r) { return l += r; }

    friend mint operator-(mint l, const mint &r) { return l -= r; }

    friend mint operator*(mint l, const mint &r) { return l *= r; }

    mint & operator--() { if (--x == -1) x = M - 1; return *this; }

    mint & operator++() { if (++x == M) x = 0; return *this; }

    mint operator--(int) { mint temp = *this; --*this; return temp; }

    mint operator++(int) { mint temp = *this; ++*this; return temp; }

    mint operator-() const { return 0 - *this; }

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

    friend bool operator==(const mint &l, const mint &r) { return l.x == r.x; }

    friend bool operator!=(const mint &l, const mint &r) { return l.x != r.x; }

    friend ostream & operator<<(ostream &out, const mint &a) { return out << a.x; }

    mint pow(long long e = M - 2) const {
        mint ans = 1, b = *this;
        while (e > 0) {
            if (e % 2 == 1) {
                ans *= b;
            }
            b *= b;
            e /= 2;
        }
        return ans;
    }
};

mint ways[N][N][L][3];
int a[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, l;
    cin >> n >> l;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a, a + n);

    if (n == 1) {
        cout << 1 << "\n";
        exit(0);
    }

    ways[0][0][0][0] = 1;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            for (int k = 0; k <= l; ++k) {
                for (int p = 0; p <= 2; ++p) {
                    int k_new = k + (2 * j - p) * (i > 0 ? a[i] - a[i - 1] : 0);
                    if (k_new > l || ways[i][j][k][p] == 0) {
                        continue;
                    }

                    if (j >= 2) {
                        ways[i + 1][j - 1][k_new][p] += (j - 1) * ways[i][j][k][p];
                    }

                    if (j >= 1) {
                        ways[i + 1][j][k_new][p] += (2 * j - p) * ways[i][j][k][p];
                        if (p < 2) {
                            ways[i + 1][j][k_new][p + 1] += (2 - p) * ways[i][j][k][p];
                        }
                    }

                    ways[i + 1][j + 1][k_new][p] += (j + 1 - p) * ways[i][j][k][p];
                    if (p < 2) {
                        ways[i + 1][j + 1][k_new][p + 1] += (2 - p) * ways[i][j][k][p];
                    }
                }
            }
        }
    }

    mint ans = 0;
    for (int i = 0; i <= l; ++i) {
        ans += ways[n][1][i][2];
    }

    cout << ans << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80