oj.uz

Submission #951896

# Submission time Handle Problem Language Result Execution time Memory
951896 2024-03-22T22:13:31 Z vjudge1 Skyscraper (JOI16_skyscraper) C++17
15 / 100
 148 ms 347468 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) {
    LL inc = h[n + 1] - h[n], ends = 2 * k - st - en;
    l -= ends * inc;
    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;

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

    add(ret, call(n - 1, k + 1, l, st, en));
    if(!st) add(ret, call(n - 1, k + 1, l, 1, en));
    if(!en) add(ret, call(n - 1, k + 1, l, 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, l, 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];
    LL ans = 0;

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

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:66:8: warning: unused variable 'ans' [-Wunused-variable]
   66 |     LL ans = 0;
      |        ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 148 ms 347220 KB Output is correct
3 Correct 69 ms 347168 KB Output is correct
4 Correct 70 ms 347212 KB Output is correct
5 Correct 72 ms 347216 KB Output is correct
6 Correct 70 ms 347212 KB Output is correct
7 Correct 71 ms 347468 KB Output is correct
8 Correct 70 ms 347132 KB Output is correct
9 Incorrect 70 ms 347220 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 347272 KB Output is correct
2 Correct 69 ms 347152 KB Output is correct
3 Correct 74 ms 347176 KB Output is correct
4 Correct 70 ms 347288 KB Output is correct
5 Correct 70 ms 347216 KB Output is correct
6 Correct 72 ms 347216 KB Output is correct
7 Correct 69 ms 347284 KB Output is correct
8 Correct 95 ms 347224 KB Output is correct
9 Correct 72 ms 347328 KB Output is correct
10 Correct 72 ms 347220 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 148 ms 347220 KB Output is correct
3 Correct 69 ms 347168 KB Output is correct
4 Correct 70 ms 347212 KB Output is correct
5 Correct 72 ms 347216 KB Output is correct
6 Correct 70 ms 347212 KB Output is correct
7 Correct 71 ms 347468 KB Output is correct
8 Correct 70 ms 347132 KB Output is correct
9 Incorrect 70 ms 347220 KB Output isn't correct
10 Halted 0 ms 0 KB -