Submission #1123842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123842		ReLice	Skyscraper (JOI16_skyscraper)	C++20	15 / 100	176 ms	260620 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define endl "\n"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

const ll inf = 1e9;
const ll N = 1e2 + 5;
const ll M = 1e3 + 5;
const ll mod = 1e9 + 7;

ll dp[N][N][M][3];
vector<ll> a;

ll del(ll i, ll j, ll m){
    return (a[i + 1] - a[i]) * (2 * j - m);
}

signed main(){
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);

    ll i, j;

    ll n, l;

    cin>>n>>l;

    a.resize(n);
    for(auto &i : a) cin>>i;

    sort(all(a));

    a.pb(a.back());

    memset(dp, 0, sizeof(dp));

    dp[0][0][0][0] = 1;

    for(i=0;i<n;i++){
        for(j=0;j<=(n + 1) / 2;j++){
            for(ll k=0;k<=l;k++){
                for(ll m=0;m<3;m++){
                    if(dp[i][j][k][m] == 0) continue;

                    dp[i][j][k][m] %= mod;

                    //cout<<i<<' '<<j<<' '<<k<<' '<<m<<endl;
                    //cout<<dp[i][j][k][m]<<endl;

                    //new without endpoint
                    dp[i + 1][j + 1][k + del(i, j + 1, m)][m] += dp[i][j][k][m];
                    //new with endpoint
                    if(m < 2) dp[i + 1][j + 1][k + del(i, j + 1, m + 1)][m + 1] += (2 - m) * dp[i][j][k][m] % mod;

                    if(j == 0) continue;
                    //part of existing without endpoint
                    dp[i + 1][j][k + del(i, j, m)][m] += (2 * j - m) * dp[i][j][k][m] % mod;
                    //part of existing with endpoint
                    if(m == 1 && i == n - 1) dp[i + 1][j][k + del(i, j, m + 1)][m + 1] += dp[i][j][k][m] % mod;
                    else if(m < 2) dp[i + 1][j][k + del(i, j, m + 1)][m + 1] += (j - m) * (2 - m) * dp[i][j][k][m] % mod;

                    //join two components
                    if(m == 2 && i == n - 1) dp[i + 1][j - 1][k + del(i, j - 1, m)][m] += dp[i][j][k][m] % mod;
                    else dp[i + 1][j - 1][k + del(i, j - 1, m)][m] += (j - m) * (j - 1) * dp[i][j][k][m] % mod;
                }
            }
        }
    }

    ll ans = 0;

    for(i=0;i<=l;i++) ans = (ans + dp[n][1][i][2]) % mod;

    cout<<ans<<endl;
}
/*

*/

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