oj.uz

답안 #361381

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361381 2021-01-29T16:26:03 Z jumpOverTheWall Skyscraper (JOI16_skyscraper) C++14
0 / 100
 94 ms 173832 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 && cLef && cRig;
    /// 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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 173804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 94 ms 173832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 173804 KB Output isn't correct
2 Halted 0 ms 0 KB -