oj.uz

Submission #951844

# Submission time Handle Problem Language Result Execution time Memory
951844 2024-03-22T20:22:10 Z vjudge1 Skyscraper (JOI16_skyscraper) C++17
15 / 100
 135 ms 347352 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

using LL = long long;
using PII = pair <int, int>;

mt19937_64 rnd(chrono :: steady_clock :: now().time_since_epoch().count());

#ifdef LEL
#include "dbg.h"
#else
#define dbg(...) {/*temon kichu na*/}
#endif
/*....................................................................*/ 

const LL MOD = 1e9 + 7;

const int N = 105, L = 1005;
LL dp[N][N][L][2][2], h[N];

void add(LL &x, LL y) {
    x += y;
    x -= MOD * (x >= MOD);
}
LL mul(LL x, LL y) {
    return x * y % MOD;
}

LL call(int n, int k, int l, int st, int en) {
    if(l < 0) return 0;
    if(n > 0 and k == 1 and st and en) return 0;
    if(n < 1) return (k == 1 and st and en);

    LL &ret = dp[n][k][l][st][en];
    if(ret != -1) return ret;

    ret = 0;
    LL inc = h[n + 1] - h[n], ends = 2 * k - st - en, lnw = l - ends * inc;

    add(ret, mul(ends, call(n - 1, k, lnw, st, en)));
    if(!st) add(ret, mul(k - (en and k > 1), call(n - 1, k, lnw, 1, en)));
    if(!en) add(ret, mul(k - (st and k > 1), call(n - 1, k, lnw, st, 1)));

    add(ret, call(n - 1, k + 1, lnw, st, en));
    if(!st) add(ret, call(n - 1, k + 1, lnw, 1, en));
    if(!en) add(ret, call(n - 1, k + 1, lnw, st, 1));

    LL comb = mul(k - 1, k - st - en);
    if(st and en and k == 2) add(comb, 1);

    if(k > 1) add(ret, mul(comb, call(n - 1, k - 1, lnw, st, en)));

    return ret;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, l;
    cin >> n >> l;
    for(int i = 1; i <= n; i++) cin >> h[i];
    sort(h + 1, h + n + 1);
    h[n + 1] = h[n];

    if(n == 1) cout << 1 << '\n';
    else {
        memset(dp, -1, sizeof dp);
        cout << call(n, 0, l, 0, 0) << '\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 135 ms 347268 KB Output is correct
3 Correct 97 ms 347344 KB Output is correct
4 Correct 98 ms 347216 KB Output is correct
5 Incorrect 125 ms 347332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 347220 KB Output is correct
2 Correct 83 ms 347204 KB Output is correct
3 Correct 82 ms 347352 KB Output is correct
4 Correct 85 ms 347148 KB Output is correct
5 Correct 90 ms 347216 KB Output is correct
6 Correct 86 ms 347220 KB Output is correct
7 Correct 85 ms 347188 KB Output is correct
8 Correct 79 ms 347216 KB Output is correct
9 Correct 80 ms 347216 KB Output is correct
10 Correct 82 ms 347316 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 135 ms 347268 KB Output is correct
3 Correct 97 ms 347344 KB Output is correct
4 Correct 98 ms 347216 KB Output is correct
5 Incorrect 125 ms 347332 KB Output isn't correct
6 Halted 0 ms 0 KB -