Submission #386161

#	Time	Username	Problem	Language	Result	Execution time	Memory
386161		Vladth11	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	624 ms	320236 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) {
    x += v;
    x %= MOD;
}

ll Compute(ll pz, ll score, ll components, ll st, ll dr) {
    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];
    }
    if(pz == n) {
        ll sol = 0;
        if(st == 0 && dr == 0) {
            return dp[pz][score][components][st][dr] = 0;
        }
        if(components == 1) {
            if(st == 0) {
                sol++;
            }
            if(dr == 0) {
                sol++;
            }
            return dp[pz][score][components][st][dr] = sol;
        }
        if(components == 2) {
            if(st + dr != 2) {
                return dp[pz][score][components][st][dr] = sol;
            }
            sol++;
            return dp[pz][score][components][st][dr] = sol;
        }
        return 0;
    }
    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);
    cout << Compute(1, 0, 0, 0, 0);
    return 0;
}

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