Submission #1150130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150130		hahahoang132	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	89 ms	7180 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
const ll base = 37;
const ll inf = LLONG_MAX/4;
const ll mod = 1e9 + 7;
#define bit(x,y) ((x >> y) & 1)
ll d[2][105][1005][2][2];
ll a[105];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll i,j;
    ll n,l;
    cin >> n >> l;
    if(n == 1) 
    {
        cout << 1;
        return 0;
    }
    for(i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1,a + 1 + n);
    if(n == 2)
    {
        if(abs(a[2] - a[1]) <= l) cout << 2;
        else cout << 0;
        return 0;
    }
    ll e = 0;
    d[e][1][0][0][0] = 1;
    d[e][1][0][0][1] = 1;
    d[e][1][0][1][0] = 1;
    for(i = 2;i <= n;i++)
    {
        for(ll i1 = 1;i1 <= n;i1++)
        {
            for(ll i2 = 0;i2 <= l;i2++)
            {
                for(ll cd = 0;cd <= 1;cd++)
                {
                    for(ll cc = 0;cc <= 1;cc++)
                    {
                        ll t = d[e][i1][i2][cd][cc];
                        ll ni2 = i2 + (a[i] - a[i - 1]) * (2 * i1 - cd - cc);
                        d[e][i1][i2][cd][cc] = 0;
                        if(t == 0 || ni2 > l) continue;
                        d[1 - e][i1 + 1][ni2][cd][cc] += ((i1 - cd - cc + 1) * t) % mod;
                        d[1 - e][i1 + 1][ni2][cd][cc] %= mod;
                        if(cd == 0)
                        {
                            d[1 - e][i1 + 1][ni2][1][cc] += t;
                            d[1 - e][i1 + 1][ni2][1][cc] %= mod;
                        }
                        if(cc == 0)
                        {
                            d[1 - e][i1 + 1][ni2][cd][1] += t;
                            d[1 - e][i1 + 1][ni2][cd][1] %= mod;
                        }
                        d[1 - e][i1][ni2][cd][cc] += ((i1 * 2 - cd - cc) * t) % mod;
                        d[1 - e][i1][ni2][cd][cc] %= mod;
                        if(cd == 0)
                        {
                            d[1 - e][i1][ni2][1][cc] += t;
                            d[1 - e][i1][ni2][1][cc] %= mod;
                        }
                        if(cc == 0)
                        {
                            d[1 - e][i1][ni2][cd][1] += t;
                            d[1 - e][i1][ni2][cd][1] %= mod;
                        }
                        d[1 - e][i1 - 1][ni2][cd][cc] += ((i1 - 1) * t) % mod;
                        d[1 - e][i1 - 1][ni2][cd][cc] %= mod;
                    }
                }
            }
        }
        e = 1 - e;
    }
    ll ans = 0;
    for(i = 0;i <= l;i++)
    {
        ans += d[e][1][i][1][1];
        ans %= mod;
    }
    cout << ans;
}

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