제출 #1123853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123853		ReLice	Skyscraper (JOI16_skyscraper)	C++20	20 / 100	64 ms	36420 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;

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;

    if(n == 1) return cout<<1, 0;

    a.pb(0);
    sort(all(a));

    a.pb(inf);

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

    for(i=1;i<=n;i++){
        for(j=1;j<=i;j++){
            for(ll k=0;k<=l;k++){
                for(ll m=0;m<3;m++){
                    ll c = (a[i + 1] - a[i]) * (2 * j - m);

                    if(k - c < 0 || i + j + 1 - m > n) continue;

                    //new without end
                    dp[i][j][k][m] += dp[i - 1][j - 1][k - c][m];

                    //new with end
                    if(m) dp[i][j][k][m] += dp[i - 1][j - 1][k - c][m - 1] * (3 - m);

                    //old without end
                    dp[i][j][k][m] += (j * 2 - m) * dp[i - 1][j][k - c][m];

                    //old with end
                    if(m == 1) dp[i][j][k][m] += 2 * j * dp[i - 1][j][k - c][m - 1];
                    else if(m){
                        if(i == n) dp[i][j][k][m] += dp[i - 1][j][k - c][m - 1];
                        else if(j > 1) dp[i][j][k][m] += (j - 1) * dp[i - 1][j][k - c][m - 1];
                    }

                    //join two
                    if(m == 2){
                        if(i == n) dp[i][j][k][m] += dp[i - 1][j + 1][k - c][m];
                        else dp[i][j][k][m] += j * (j - 1) * dp[i - 1][j + 1][k - c][m];
                    }
                    else dp[i][j][k][m] += j * (j + 1 - m) * dp[i - 1][j + 1][k - c][m];

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

    ll ans = 0;

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

    cout<<ans<<endl;
}
/*

*/

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