oj.uz

Submission #361382

# Submission time Handle Problem Language Result Execution time Memory
361382 2021-01-29T16:26:27 Z jumpOverTheWall Skyscraper (JOI16_skyscraper) C++14
100 / 100
 350 ms 174112 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 173964 KB Output is correct
2 Correct 95 ms 173952 KB Output is correct
3 Correct 92 ms 173804 KB Output is correct
4 Correct 93 ms 173804 KB Output is correct
5 Correct 94 ms 173824 KB Output is correct
6 Correct 92 ms 173804 KB Output is correct
7 Correct 98 ms 173804 KB Output is correct
8 Correct 93 ms 173804 KB Output is correct
9 Correct 93 ms 173804 KB Output is correct
10 Correct 93 ms 173804 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 173804 KB Output is correct
2 Correct 93 ms 173804 KB Output is correct
3 Correct 93 ms 173804 KB Output is correct
4 Correct 93 ms 173932 KB Output is correct
5 Correct 94 ms 173804 KB Output is correct
6 Correct 94 ms 173804 KB Output is correct
7 Correct 93 ms 173784 KB Output is correct
8 Correct 93 ms 173824 KB Output is correct
9 Correct 95 ms 173804 KB Output is correct
10 Correct 92 ms 173804 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 173964 KB Output is correct
2 Correct 95 ms 173952 KB Output is correct
3 Correct 92 ms 173804 KB Output is correct
4 Correct 93 ms 173804 KB Output is correct
5 Correct 94 ms 173824 KB Output is correct
6 Correct 92 ms 173804 KB Output is correct
7 Correct 98 ms 173804 KB Output is correct
8 Correct 93 ms 173804 KB Output is correct
9 Correct 93 ms 173804 KB Output is correct
10 Correct 93 ms 173804 KB Output is correct
11 Correct 92 ms 173804 KB Output is correct
12 Correct 93 ms 173804 KB Output is correct
13 Correct 93 ms 173804 KB Output is correct
14 Correct 93 ms 173932 KB Output is correct
15 Correct 94 ms 173804 KB Output is correct
16 Correct 94 ms 173804 KB Output is correct
17 Correct 93 ms 173784 KB Output is correct
18 Correct 93 ms 173824 KB Output is correct
19 Correct 95 ms 173804 KB Output is correct
20 Correct 92 ms 173804 KB Output is correct
21 Correct 95 ms 173804 KB Output is correct
22 Correct 350 ms 174112 KB Output is correct
23 Correct 316 ms 173804 KB Output is correct
24 Correct 282 ms 173804 KB Output is correct
25 Correct 321 ms 173932 KB Output is correct
26 Correct 268 ms 173804 KB Output is correct
27 Correct 147 ms 174060 KB Output is correct
28 Correct 173 ms 173804 KB Output is correct
29 Correct 264 ms 173864 KB Output is correct
30 Correct 324 ms 173932 KB Output is correct