Submission #382285

#	Time	Username	Problem	Language	Result	Execution time	Memory
382285		gevacrt	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	419 ms	12032 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define int ll

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, L; cin >> N >> L;
    vi A(N); for(auto &i : A) cin >> i;
    sort(all(A));

    if(N == 1){
        cout << 1 << endl;
        return 0;
    }

    vector<vvi> dp(L+5, vvi(N+5, vi(3))), DP = dp;
    dp[0][0][0] = 1;

    for(int x = 0; x < N; x++){
        for(int cost = 0; cost <= L; cost++){
            for(int groups = 0; groups <= x+1; groups++){
                for(int endpoints = 0; endpoints <= 2; endpoints++){
                    int increase = (2*groups-endpoints)*(A[x]-(x?A[x-1]:0));
                    if(cost+increase < 0 or cost+increase > L) continue;

                    int CVAL = dp[cost][groups][endpoints];
                    auto &JP = DP[cost+increase];

                    // create a new component
                    JP[groups+1][endpoints] += CVAL;
                    // create new endpoint component
                    if(endpoints == 0) JP[groups+1][1] += 2*CVAL;
                    else if(endpoints == 1) JP[groups+1][2] += CVAL;
                    // extend a component
                    JP[groups][endpoints] += (2*groups-endpoints)*CVAL;
                    // extend a component endpoint
                    if(endpoints == 0) JP[groups][1] += 2*groups*CVAL;
                    else if(endpoints == 1){
                        if(x == N-1) JP[groups][2] += groups*CVAL;
                        else JP[groups][2] += (groups-1)*CVAL;
                    }
                    // Merge two components
                    if(groups > 1){
                        if(endpoints == 0) JP[groups-1][endpoints] += groups*(groups-1)*CVAL;
                        else if(endpoints == 1) JP[groups-1][endpoints] += (groups-1)*(groups-1)*CVAL;
                        else if(x == N-1) JP[groups-1][endpoints] += CVAL;
                        else JP[groups-1][endpoints] += (groups-1)*(groups-2)*CVAL;
                    }
                }
            }
        }
        for(int cost = 0; cost <= L; cost++)
            for(int groups = 0; groups <= N; groups++)
                for(int endpoints = 0; endpoints <= 2; endpoints++)
                    DP[cost][groups][endpoints] %= MOD, dp[cost][groups][endpoints] = 0;

        swap(dp, DP);
    }

    int ans = 0;
    for(int cost = 0; cost <= L; cost++)
        ans += dp[cost][1][2], ans %= MOD;
    cout << ans << endl;

    return 0;
}

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