Submission #39903

#	Time	Username	Problem	Language	Result	Execution time	Memory
39903		nickyrio	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	329 ms	269136 KiB

skyscraper

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 111
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
using namespace std;

int n, a[N], lim;

const int MOD = 1e9 + 7;
bool used[N][N][N * 10][2][2];
int dp[N][N][N * 10][2][2];
// 1 : Put u positions
// 2 : Now have cc connected components
// 3 : Different equal diff
// 4 : Front is chosen
// 5 : Back is chosen
void Add(int &a, int b) { a += b; if (a >= MOD) a -= MOD; }
int Mul(int a, int b) { return 1ll * a * b % MOD; }

int cal(int u, int cc, int diff, int fc, int bc) {
    diff += u == 0 ? 0 : (a[u] - a[u - 1]) * (2 * cc - fc - bc);
    if (diff > lim) return 0;
    if (u == n) {
        if (!(fc & bc)) return 0;
        return cc == 1;
    }
    if (used[u][cc][diff][fc][bc]) return dp[u][cc][diff][fc][bc];
    used[u][cc][diff][fc][bc] = 1;

    int &ret = dp[u][cc][diff][fc][bc] = 0;
    // Create new connected component
        Add(ret, Mul(cal(u + 1, cc + 1, diff, fc, bc), cc + 1 - fc - bc));
        // At front
        if (!fc) Add(ret, cal(u + 1, cc + 1, diff, 1, bc));
        // At back
        if (!bc) Add(ret, cal(u + 1, cc + 1, diff, fc, 1));
    if (cc > 0) {
    // Connect two components
        if (cc > 1) Add(ret, Mul(cal(u + 1, cc - 1, diff, fc, bc), cc - 1));
    //Enlarge connected component
        Add(ret, Mul(cal(u + 1, cc, diff, fc, bc), 2 * cc - fc - bc));
        // At front
        if (!fc) Add(ret, cal(u + 1, cc, diff, 1, bc));
        // At back
        if (!bc) Add(ret, cal(u + 1, cc, diff, fc, 1));
    }
    return ret;
}


int main() {
    IO;
    cin >> n >> lim;
    REP(i, n) cin >> a[i];
    if (n == 1) {
        cout << 1;
        return 0;
    }
    sort(a, a + n);
    cout << cal(0, 0, 0, 0, 0);
}

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