Submission #524685

#	Time	Username	Problem	Language	Result	Execution time	Memory
524685		LptN21	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	37 ms	2848 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define FF first
#define SS second
#define eps 1e-9
#define PI aocs(-1.0)
// VECTOR (6)
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
#define ub upper_bound
#define uniq(x) sort(all((x))), (x).resize(unique(all((x))) - (x).begin());
// BIT (6)
#define BIT(x, i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))
#define CNTBIT(x) __builtin_popcountll(x)
#define ODDBIT(x) __builtin_parityll(x)
#define SUBSET(big, small) (((big)&(small))==(small))
#define FIRSTBIT(x) __builtin_ctzll(x)
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> ii;

/* */
template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}
/* */

/* CODE BELOW */
const int N = 100 + 7, M = 1000 + 7;
const int MOD = 1e9 + 7;
const int oo = 1e9 + 7;

int n, l, a[N];
int _dp[2][N][M][3];

//
int add(int a, int b) {
    a+= b; if(a>=MOD) a-=MOD;
    return a;
}
int mul(int a, int b) {
    return (1LL * a * b)%MOD;
}
void update(int &a, int b) {
    a+= b; if(a>=MOD) a-=MOD;
}
//

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    fastIO;
    cin>>n>>l;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1, a+n+1); a[0] = 0;

    //_dp[0][0][0][0] = 1;
    _dp[1][1][0][0] = 1;
    _dp[1][1][0][1] = 2;
    _dp[1][1][0][2] = 1;
    int cur = 1, nxt = 0;
    for(int i=1;i<n;i++, swap(cur, nxt)) {
        memset(_dp[nxt], 0, sizeof _dp[nxt]);
        int diff = a[i+1] - a[i];
        for(int j=1;j<=i;j++) for(int k=0;k<=l;k++) for(int t=0;t<3;t++) {
            int v = _dp[cur][j][k][t]; if(!v) continue;
            int nwDiff = k + diff * (2*j - t); if(nwDiff > l) continue;
            // append left/right
            if(2*j>t) update(_dp[nxt][j][nwDiff][t], mul(v, 2*j-t));

            if(t<2) update(_dp[nxt][j][nwDiff][t+1], mul(v, 2-t));

            // connect 2 component
            if(j>1) update(_dp[nxt][j-1][nwDiff][t], mul(v, j-1));

            // add new component
            if(j+1>t) update(_dp[nxt][j+1][nwDiff][t], mul(v, j+1-t));

            if(t<2) update(_dp[nxt][j+1][nwDiff][t+1], mul(v, 2-t));
        }
    }

    int ans = 0;
    for(int i=0;i<=l;i++) update(ans, _dp[cur][1][i][2]);
    cout<<ans;

    return 0;
}

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