Submission #386166

#	Time	Username	Problem	Language	Result	Execution time	Memory
386166		Vladth11	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	823 ms	316908 KiB

skyscraper

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 201;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 21;

ll dp[101][1001][101][2][2];
ll n, L;
ll v[101];

void add(ll &x, ll v) {
    v = max(0LL, v);
    x += v;
    x %= MOD;
}

ll Compute(ll pz, ll score, ll components, ll st, ll dr) {
    if(pz == n + 1) {
        return (score <= L && components == 1 && st == 1 && dr == 1);
    }
    if(pz > 1)
        score += (v[pz] - v[pz - 1]) * (2 * components - st - dr);
    if(score > L)
        return 0;
    if(dp[pz][score][components][st][dr] != -1) {
        return dp[pz][score][components][st][dr];
    }
    ll sol = 0;
    ///1. v[pz] il punem ca st
    if(st != 1) {
        //if(!(dr == 1 && components == 1)){
        ///propria componenta
        add(sol, Compute(pz + 1, score, components + 1, 1, dr));
        ///la ce mai din stanga componenta
        if(components > 0)
            add(sol, Compute(pz + 1, score, components, 1, dr));
        //}
    }
    if(dr != 1) {
        //if(!(st == 1 && components == 1)) {
        add(sol, Compute(pz + 1, score, components + 1, st, 1));
        if(components > 0)
            add(sol, Compute(pz + 1, score, components, st, 1));
        // }

    }
    ///o componenta noua
    add(sol, (Compute(pz + 1, score, components + 1, st, dr) * (components + 1 - st - dr)) % MOD);
    ///alipim in stanga unei componente
    if(components > 0)
        add(sol, (Compute(pz + 1, score, components, st, dr) * (components - st)) % MOD);
    ///alipim in dreapta unei componente
    if(components > 0)
        add(sol, (Compute(pz + 1, score, components, st, dr) * (components - dr)) % MOD);
    ///mergeuim doua componente
    if(components > 1)
        add(sol, (Compute(pz + 1, score, components - 1, st, dr) * (components - 1)) % MOD);
    return dp[pz][score][components][st][dr] = sol;
}

int main() {
    //memset(dp, -1, sizeof(dp));
    cin >> n >> L;
    if(n == 1) {
        cout << 1;
        return 0;
    }
    for(int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);
    dp[0][0][0][0][0] = 1;
    v[0] = v[1];
    ll sol = 0;
    for(int i = 1; i <= n; i++){
        for(int score = 0; score <= L; score++){
            for(int components = 1; components <= i; components++){
                for(int st = 0; st <= 1; st++){
                    for(int dr = 0; dr <= 1; dr++){
                        if(st == 1){
                            ///v[i] si-a deschis o noua comp care e stanga
                            ll inainte = score - ((v[i] - v[i - 1]) * ((components - 1) * 2 - dr));
                            if(inainte >= 0)
                                add(dp[i][score][components][st][dr], dp[i - 1][inainte][components - 1][0][dr]);
                            ///se alipeste la cea mai din stanga si devine st
                            inainte = score - ((v[i] - v[i - 1]) * (components * 2 - dr));
                            if(inainte >= 0)
                                add(dp[i][score][components][st][dr], dp[i - 1][inainte][components][0][dr]);
                        }
                        if(dr == 1){
                            ll inainte = score - ((v[i] - v[i - 1]) * ((components - 1) * 2 - st));
                            if(inainte >= 0)
                                add(dp[i][score][components][st][dr], dp[i - 1][inainte][components - 1][st][0]);
                            inainte = score - ((v[i] - v[i - 1]) * (components * 2 - st));
                            if(inainte >= 0)
                                add(dp[i][score][components][st][dr], dp[i - 1][inainte][components][st][0]);
                        }
                        ///deschide noua componenta
                        ll inainte = score - ((v[i] - v[i - 1]) * ((components - 1) * 2 - st - dr));
                        if(inainte >= 0)
                        add(dp[i][score][components][st][dr], (dp[i - 1][inainte][components - 1][st][dr] * (components - st - dr)) % MOD);
                        ///se alipeste in stanga unei componente
                        inainte = score - ((v[i] - v[i - 1]) * (components * 2 - st - dr));
                        if(inainte >= 0)
                        add(dp[i][score][components][st][dr], (dp[i - 1][inainte][components][st][dr] * (components - st)) % MOD);
                        ///se alipeste in dreapta unei componente
                        inainte = score - ((v[i] - v[i - 1]) * (components * 2 - st - dr));
                        if(inainte >= 0)
                        add(dp[i][score][components][st][dr], (dp[i - 1][inainte][components][st][dr] * (components - dr)) % MOD);
                        ///mergeuieste doua componente
                        inainte = score - ((v[i] - v[i - 1]) * ((components + 1) * 2 - st - dr));
                        if(inainte >= 0)
                        add(dp[i][score][components][st][dr], (dp[i - 1][inainte][components + 1][st][dr] * components) % MOD);
                        if(i == n && st == 1 && dr == 1 && components == 1){
                            add(sol, dp[i][score][components][st][dr]);
                        }
                    }
                }
            }
        }
    }
    cout << sol;
    return 0;
}

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