Submission #1251880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251880		vnedu	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	250 ms	321860 KiB

skyscraper

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

const int N = 100 + 5;
const int L = 1000 + 5;
const int mod = 1e9 + 7;
int n,l,a[N];
long long dp[N][N][1<<2][L];
void solve()
{
    cin>>n>>l;
    if(n==1) return void(cout<<1);
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    dp[0][0][0][0]=1;
    for(int i=0;i<=n;++i)
    {
        for(int j=0;j<=n;++j)
        {
            for(int b=0;b<(1<<2);++b)
            {
                for(int k=0;k<=l;++k)
                {
                    long long &cur=dp[i][j][b][k];
                    cur%=mod;
                    if(i<n && cur)
                    {
//                        cout<<i<<' '<<j<<' '<<b<<' '<<k<<"   "<<cur<<'\n';
                        int cnt=2*j-__builtin_popcount(b);
                        int diff=a[i+1]-a[i];
                        int kdot=k+cnt*diff;
                        if(kdot<=l)
                        {
                            // gop 2p
                            if(j>=2) dp[i+1][j-1][b][kdot]+=cur*1LL*(j-1)%mod;
                            // chen 1p
                            if(j)
                            {
                                dp[i+1][j][b][kdot]+=cur*1LL*cnt%mod;
                                if(!(b>>0&1)) dp[i+1][j][b|(1<<0)][kdot]+=cur;
                                if(!(b>>1&1)) dp[i+1][j][b|(1<<1)][kdot]+=cur;
                            }
                            // tao 1p
                            dp[i+1][j+1][b][kdot]+=cur*1LL*(j+1-__builtin_popcount(b))%mod;
                            if(!(b>>0&1)) dp[i+1][j+1][b|(1<<0)][kdot]+=cur;
                            if(!(b>>1&1)) dp[i+1][j+1][b|(1<<1)][kdot]+=cur;
                        }
                    }
                }
            }
        }
    }
    long long ans=0;
    for(int k=0;k<=l;++k) ans+=dp[n][1][(1<<2)-1][k];
    cout<<(ans%=mod);
}
int main(void)
{
//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int testcase=1;
//    cin>>testcase;
    while(testcase--)
        solve();
//    cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return 0;
}

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