oj.uz

Submission #168845

# Submission time Handle Problem Language Result Execution time Memory
168845 2019-12-16T16:33:43 Z srvlt Skyscraper (JOI16_skyscraper) C++14
5 / 100
 123 ms 125664 KB 
#include <bits/stdc++.h>

#define ll long long
#define db double
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define endl "\n"

//#define int long long

using namespace std;

const int N = 103, K = 1003, MOD = 1e9 + 7;
int n, r, a[N], dp[N][N][K][3];

void add(int & x, int y) {
    x += y;
    if (x >= MOD) {
        x %= MOD;
    }
}

int calc(int i, int j, int k, int l) {
    if (i > 0 && (j < 1 || l > 2 || k > r)) {
        return 0;
    }
    if (i == n) {
        return j == 1 && l == 2;
    }
    int & res = dp[i][j][k][l];
    if (res != -1) {
        return res;
    }
    int s = (a[i + 1] - a[i]) * (2 * j - l) + k;
    res = 0;
    add(res, (j + 1 - l) * calc(i + 1, j + 1, s, l));
    add(res, (2 - l) * calc(i + 1, j, s, l + 1));
    add(res, (2 - l) * calc(i + 1, j + 1, s, l + 1));
    add(res, (j - 1) * calc(i + 1, j - 1, s, l));
    add(res, (2 * j - l) * calc(i + 1, j, s, l));
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(dp, -1, sizeof(dp));
    cin >> n >> r;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (n == 1) {
        cout << 1;
        return 0;
    }
    sort(a + 1, a + n + 1);
    a[0] = a[1];
    cout << calc(0, 0, 0, 0);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 125432 KB Output is correct
2 Correct 108 ms 125264 KB Output is correct
3 Correct 107 ms 125312 KB Output is correct
4 Correct 107 ms 125304 KB Output is correct
5 Correct 107 ms 125304 KB Output is correct
6 Correct 109 ms 125304 KB Output is correct
7 Correct 108 ms 125304 KB Output is correct
8 Correct 123 ms 125276 KB Output is correct
9 Correct 108 ms 125304 KB Output is correct
10 Correct 107 ms 125304 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 125664 KB Output is correct
2 Correct 108 ms 125228 KB Output is correct
3 Correct 108 ms 125304 KB Output is correct
4 Correct 107 ms 125292 KB Output is correct
5 Correct 108 ms 125276 KB Output is correct
6 Correct 108 ms 125304 KB Output is correct
7 Correct 107 ms 125304 KB Output is correct
8 Correct 108 ms 125304 KB Output is correct
9 Incorrect 108 ms 125428 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 125432 KB Output is correct
2 Correct 108 ms 125264 KB Output is correct
3 Correct 107 ms 125312 KB Output is correct
4 Correct 107 ms 125304 KB Output is correct
5 Correct 107 ms 125304 KB Output is correct
6 Correct 109 ms 125304 KB Output is correct
7 Correct 108 ms 125304 KB Output is correct
8 Correct 123 ms 125276 KB Output is correct
9 Correct 108 ms 125304 KB Output is correct
10 Correct 107 ms 125304 KB Output is correct
11 Correct 108 ms 125664 KB Output is correct
12 Correct 108 ms 125228 KB Output is correct
13 Correct 108 ms 125304 KB Output is correct
14 Correct 107 ms 125292 KB Output is correct
15 Correct 108 ms 125276 KB Output is correct
16 Correct 108 ms 125304 KB Output is correct
17 Correct 107 ms 125304 KB Output is correct
18 Correct 108 ms 125304 KB Output is correct
19 Incorrect 108 ms 125428 KB Output isn't correct
20 Halted 0 ms 0 KB -