Submission #361382

#	Time	Username	Problem	Language	Result	Execution time	Memory
361382		jumpOverTheWall	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	350 ms	174112 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int N = 105;
const int L = 1005;
const int MOD = 1000000007;

int dp[N][L][N][2][2], a[N], n, lim;

int add(int x, int y) {
    if ((x += y) >= MOD) x -= MOD;
    return x;
}

int mul(int x, int y) {
    return (long long)x * y % MOD;
}

int calc(int i, int cSum, int cMid, int cLef, int cRig) {
    int &res = dp[i][cSum][cMid][cLef][cRig];
    if (res >= 0) return res; res = 0;
    /// assume missing position is filled with a[i + 1]
    int nSum = cSum + (cMid * 2 + cLef + cRig) * (a[i + 1] - a[i]);
    if (nSum > lim || cMid < 0) return res = 0;
    /// concate left segment and right segment
    if (i == n - 1) return res = cMid == 0;
    /// append to left segment
    res = add(res, calc(i + 1, nSum, cMid, 1, cRig));
    /// append to right segment
    res = add(res, calc(i + 1, nSum, cMid, cLef, 1));
    /// create new mid segment
    res = add(res, mul(calc(i + 1, nSum, cMid + 1, cLef, cRig), cMid + 1));
    /// append to mid segment
    res = add(res, mul(calc(i + 1, nSum, cMid, cLef, cRig), cMid * 2));
    /// concate two adjacent mid segments
    res = add(res, mul(calc(i + 1, nSum, cMid - 1, cLef, cRig), cMid - 1));
    /// concate left segment and leftest mid segment
    res = add(res, calc(i + 1, nSum, cMid - 1, 1, cRig));
    /// concate right segment and rightest mid segment
    res = add(res, calc(i + 1, nSum, cMid - 1, cLef, 1));
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> lim;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    memset(dp, -1, sizeof dp);
    cout << calc(0, 0, 0, 0, 0) << '\n';
}

Compilation message (stderr)

skyscraper.cpp: In function 'int calc(int, int, int, int, int)':
skyscraper.cpp:22:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |     if (res >= 0) return res; res = 0;
      |     ^~
skyscraper.cpp:22:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |     if (res >= 0) return res; res = 0;
      |                               ^~~

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