Submission #292976

#	Time	Username	Problem	Language	Result	Execution time	Memory
292976		12tqian	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	136 ms	130588 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) {
    return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "{"; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "}"; }
const int MOD = 1e9 + 7;
typedef decay<decltype(MOD)>::type T;
struct mi {
    T val;
    explicit operator T() const { return val; }
    mi() { val = 0; }
    mi(const long long& v) {
        val = (-MOD <= v && v <= MOD) ? v : v % MOD;
        if (val < 0) val += MOD; }
    friend ostream& operator<<(ostream& os, const mi& a) { return os << a.val; }
    friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
    friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
    friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
    mi operator-() const { return mi(-val); }
    mi& operator+=(const mi& m) {
        if ((val += m.val) >= MOD) val -= MOD;
        return *this; }
    mi& operator-=(const mi& m) {
        if ((val -= m.val) < 0) val += MOD;
        return *this; }
    mi& operator*=(const mi& m) { val = (long long) val * m.val % MOD;
        return *this; }
    friend mi pow(mi a, long long p) {
        mi ans = 1; assert(p >= 0);
        for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
        return ans; }
    friend mi inv(const mi& a) { assert(a != 0); return pow(a, MOD - 2); }
    mi& operator/=(const mi& m) { return (*this) *= inv(m); }
    friend mi operator+(mi a, const mi& b) { return a += b; }
    friend mi operator-(mi a, const mi& b) { return a -= b; }
    friend mi operator*(mi a, const mi& b) { return a *= b; }
    friend mi operator/(mi a, const mi& b) { return a /= b; }
};
const int MAXN = 105;
const int MAXL = 1005;
const int INF = 10000;
mi dp[MAXN][MAXN][MAXL][3];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N, L;
    cin >> N >> L;
    vector<int> A(N + 1);
    for (int i = 0; i < N; i++) cin >> A[i];
    A[N] = INF;
    sort(A.begin(), A.end());
    if (N == 1) {
        cout << 1 << '\n';
        return 0;
    }
    int diff = A[1] - A[0];
    if (diff <= L) dp[1][1][diff][1] = 2;
    if (2  * diff <= L) dp[1][1][2 * diff][0] = 1;
    for (int i = 1; i < N; i++) {
        diff = A[i + 1] - A[i];
        for (int j = 1; j <= i; j++) {
            for (int k = 0; k <= L; k++) {
                for (int l = 0; l < 3; l++) {
                    if (dp[i][j][k][l] == 0) continue;
                    if (l < 2 && k + diff * (2 * j - l - 1) <= L) {
                        if (i == N - 1) {
                            assert(j == 1 && l == 1);
                            dp[i + 1][j][k + diff * (2 * j - l - 1)][l + 1] += dp[i][j][k][l] * (2 - l) * j;
                        } else if (l == 0 || j > 1) {
                            dp[i + 1][j][k + diff * (2 * j - l - 1)][l + 1] += dp[i][j][k][l] * (2 - l) * (j - l);
                        }
                        if (k + diff * (2 * j - l + 1) <= L) {
                            dp[i + 1][j + 1][k + diff * (2 * j - l + 1)][l + 1] += dp[i][j][k][l] * (2 - l);
                        }
                    }
                    if (k + diff * (2 * j - l + 2) <= L) {
                        dp[i + 1][j + 1][k + diff * (2 * j - l + 2)][l] += dp[i][j][k][l];
                    }
                    if (k + diff * (2 * j - l) <= L) {
                        dp[i + 1][j][k + diff * (2 * j - l)][l] += dp[i][j][k][l] * (2 * j - l);
                    }
                    if (k + diff * (2 * j - l - 2) <= L && j >= 2 && (i == N - 1 || j > 2 || l < 2)) {
                        if (l == 0) {
                            dp[i + 1][j - 1][k + diff * (2 * j - l - 2)][l] += dp[i][j][k][l] * j * (j - 1);
                        } else if (l == 1) {
                            dp[i + 1][j - 1][k + diff * (2 * j - l - 2)][l] += dp[i][j][k][l] * (j - 1) * (j - 1);
                        } else if (l == 2) {
                            if (i == N - 1) {
                                assert(j == 2);
                                dp[i + 1][j - 1][k + diff * (2 * j - l - 2)][l] += dp[i][j][k][l];
                            } else {
                                dp[i + 1][j - 1][k + diff * (2 * j - l - 2)][l] += dp[i][j][k][l] * (j - 1) * (j - 2);
                            }
                        }
                    }
                }
            }
        }
    }
    mi ans = 0;
    for (int s = 0; s <= L; s++) {
        ans += dp[N][1][s][2];
    }
    cout << ans << '\n';
    return 0;
}

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