oj.uz

답안 #306957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
306957 2020-09-26T15:11:56 Z two_sides Skyscraper (JOI16_skyscraper) C++17
100 / 100
 362 ms 173948 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int L = 1005;
const int N = 105;
const int MOD = 1e9 + 7;

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

int mmul(int x, int y) {
    return ll(x) * y % MOD;
}

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

int rec(int i, int tot,
int seg, int kl, int kr) {
    int nxt = tot + (seg * 2 + kl
    + kr) * abs(a[i + 1] - a[i]);
    if (nxt > l || seg < 0) return 0;
    if (i == n - 1) return seg == 0;
    int &res = dp[i][tot][seg][kl][kr];
    if (~res) return res;
    res = rec(i + 1, nxt, seg, 1, kr);
    res = madd(res,
    rec(i + 1, nxt, seg, kl, 1));
    res = madd(res, mmul(rec(i + 1,
    nxt, seg - 1, 1, kr), seg));
    res = madd(res, mmul(rec(i + 1,
    nxt, seg - 1, kl, 1), seg));
    res = madd(res, rec(i + 1,
    nxt, seg + 1, kl, kr));
    res = madd(res, mmul(rec(i + 1,
    nxt, seg, kl, kr), seg * 2));
    res = madd(res, mmul(rec(i + 1, nxt,
    seg - 1, kl, kr), seg * (seg - 1)));
    return res;
}

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 173816 KB Output is correct
2 Correct 97 ms 173816 KB Output is correct
3 Correct 96 ms 173944 KB Output is correct
4 Correct 94 ms 173820 KB Output is correct
5 Correct 96 ms 173816 KB Output is correct
6 Correct 96 ms 173816 KB Output is correct
7 Correct 98 ms 173944 KB Output is correct
8 Correct 95 ms 173816 KB Output is correct
9 Correct 103 ms 173812 KB Output is correct
10 Correct 98 ms 173816 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 173948 KB Output is correct
2 Correct 98 ms 173816 KB Output is correct
3 Correct 96 ms 173816 KB Output is correct
4 Correct 99 ms 173816 KB Output is correct
5 Correct 98 ms 173816 KB Output is correct
6 Correct 102 ms 173816 KB Output is correct
7 Correct 100 ms 173816 KB Output is correct
8 Correct 95 ms 173816 KB Output is correct
9 Correct 101 ms 173816 KB Output is correct
10 Correct 98 ms 173816 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 173816 KB Output is correct
2 Correct 97 ms 173816 KB Output is correct
3 Correct 96 ms 173944 KB Output is correct
4 Correct 94 ms 173820 KB Output is correct
5 Correct 96 ms 173816 KB Output is correct
6 Correct 96 ms 173816 KB Output is correct
7 Correct 98 ms 173944 KB Output is correct
8 Correct 95 ms 173816 KB Output is correct
9 Correct 103 ms 173812 KB Output is correct
10 Correct 98 ms 173816 KB Output is correct
11 Correct 98 ms 173948 KB Output is correct
12 Correct 98 ms 173816 KB Output is correct
13 Correct 96 ms 173816 KB Output is correct
14 Correct 99 ms 173816 KB Output is correct
15 Correct 98 ms 173816 KB Output is correct
16 Correct 102 ms 173816 KB Output is correct
17 Correct 100 ms 173816 KB Output is correct
18 Correct 95 ms 173816 KB Output is correct
19 Correct 101 ms 173816 KB Output is correct
20 Correct 98 ms 173816 KB Output is correct
21 Correct 98 ms 173820 KB Output is correct
22 Correct 362 ms 173816 KB Output is correct
23 Correct 312 ms 173816 KB Output is correct
24 Correct 292 ms 173816 KB Output is correct
25 Correct 314 ms 173816 KB Output is correct
26 Correct 294 ms 173848 KB Output is correct
27 Correct 158 ms 173816 KB Output is correct
28 Correct 183 ms 173816 KB Output is correct
29 Correct 313 ms 173816 KB Output is correct
30 Correct 330 ms 173816 KB Output is correct