제출 #951897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
951897		vjudge1	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	192 ms	347328 KiB

skyscraper

#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 or k < 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];

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

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80