Submission #567834

#	Time	Username	Problem	Language	Result	Execution time	Memory
567834		piOOE	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	206 ms	160208 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) ((int)size(x))
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

const int maxN = 101, MOD = 1e9 + 7, maxL = 1001;

int A[maxN], N, L;

int used[maxN][maxN][maxL][2][2];

int add(int a, int b) {
    return a + b < MOD ? a + b : a + b - MOD;
}

int mul(int a, int b) {
    return a * (ll) b % MOD;
}


//this function return # of ways, if we already put i elements, have b connected blocks, with weight = sum, t1 = true if ans[0] != '?'
int solve(int i, int b, int sum, bool t1, bool t2) {
    if (b > N || b < 0 || (i > 1 && b == 0)) {
        return 0;
    }
    if (i == N + 1) {
        return (b == 1) && t1 && t2;
    }
    int x = A[i], y = A[i - 1];
    sum = sum + (b - 1) * 2 * (x - y) + (t1 ? 0 : x - y) + (t2 ? 0 : x - y);
    if (sum > L) {
        return 0;
    }
    if (b == 1 && t1 && t2) {
        return 0;
    }
    int &ans = used[i][b][sum][t1][t2];
    if (ans != -1) {
        return ans;
    }
    ans = 0;
    if (b > 1) {
        //we can merge two blocks
        ans = add(ans, mul(b - 1, solve(i + 1, b - 1, sum, t1, t2)));
    }
    //we can place i-th in the left of a block
    if (t1) {
        if (b > 1) {
            ans = add(ans, mul(b - 1, solve(i + 1, b, sum, t1, t2)));
        }
    } else {
        ans = add(ans, mul(b, solve(i + 1, b, sum, t1, t2)));
        //i-th becomes ans[0]
        ans = add(ans, solve(i + 1, b, sum, true, t2));
    }
    //we can place i-th in the right of a block
    if (t2) {
        if (b > 1) {
            ans = add(ans, mul(b - 1, solve(i + 1, b, sum, t1, t2)));
        }
    } else {
        ans = add(ans, mul(b, solve(i + 1, b, sum, t1, t2)));
        //i-th becomes ans[n - 1]
        ans = add(ans, solve(i + 1, b, sum, t1, true));
    }
    //we can create new block
    if (t1 && t2) {
        ans = add(ans, mul(b - 1, solve(i + 1, b + 1, sum, t1, t2)));
    } else if (t2) {
        ans = add(ans, mul(b, solve(i + 1, b + 1, sum, t1, t2)));
        ans = add(ans, solve(i + 1, b + 1, sum, true, t2));
    } else if (t1) {
        ans = add(ans, mul(b, solve(i + 1, b + 1, sum, t1, t2)));
        ans = add(ans, solve(i + 1, b + 1, sum, t1, true));
    } else {
        ans = add(ans, mul(b + 1, solve(i + 1, b + 1, sum, t1, t2)));
        ans = add(ans, solve(i + 1, b + 1, sum, t1, true));
        ans = add(ans, solve(i + 1, b + 1, sum, true, t2));
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(used, -1, sizeof(used));
    cin >> N >> L;
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }
    sort(A + 1, A + N + 1);
    if (N == 1) {
        cout << 1;
        return 0;
    }
    cout << solve(1, 0, 0, 0, 0);
    return 0;
}

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