제출 #681643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681643		vjudge1	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	1556 ms	247820 KiB

skyscraper

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<long long>
#define vpii vector<pii >
#define Graph vector<vector<int> >
#define WGraph vector<vector<pii>>
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout)
#define mp(a,b) make_pair(a,b)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bound(i,j,n,m) ((i)<n&&(j)<m&&(i)>=0&&(j)>=0)
#define all(container) container.begin(),container.end()
#define fi first
#define se second
#define pub push_back
#define sqr(x) ((x)*(x))
#define LL_MAX 0x7fffffffffffffff
#define getPos(i,j,m) ((i)*m+(j))
const ll mod=1000000007;
const int offset=200001;
int dp[2][102][offset+2005*2][3];
int a[101];
int suf[101];
void solvecases(int cse)
{
    int n,l;
    cin>>n>>l;
    for(int i=0;i<n;++i)
        cin>>a[i];
    sort(a,a+n);
    for(int i=1;i<n;++i)
        a[i]=a[i]-a[0];
    a[0]=0;
    for(int i=n-1;i>=0;--i)
        suf[i]=(suf[i+1]+a[i]);
//    for(int i=0;i<n;++i)
//        cout<<a[i]<<' ';
//    cout<<'\n';
    dp[0][1][0+offset][0]=1;
    dp[0][1][0+offset][1]=2;
    dp[0][1][0+offset][2]=1;

    int cur=1;
    int sum=0;
    for(int i=1;i<n;++i)
    {
        for(int j=1;j<=i+1;++j){
            for(int cost=-2*sum-2*a[i];cost<=2005;++cost){
                for(int k=0;k<3;++k){
                    dp[cur][j][cost+offset][k]=0;
                }
            }
        }
        int prv=cur^1;
        for(int j=1;j<=min(i,n-i+1);++j)
        {
            for(int cost=max(-2*sum,-2*suf[i]);cost<=2005;++cost)
            {
                if(dp[prv][j][cost+offset][0])
                {
                    dp[cur][j+1][cost+offset-2*a[i]][0]
                    =(dp[cur][j+1][cost+offset-2*a[i]][0]+
                      (ll)dp[prv][j][cost+offset][0]*(j+1))%mod;
                    dp[cur][j+1][cost+offset-a[i]][1]
                    =(dp[cur][j+1][cost+offset-a[i]][1]+
                      (ll)dp[prv][j][cost+offset][0]*(2))%mod;
                    if(j>1&&cost+2*a[i]<=2005)
                    {
                        dp[cur][j-1][cost+offset+2*a[i]][0]
                        =(dp[cur][j-1][cost+offset+2*a[i]][0]+
                        (ll)dp[prv][j][cost+offset][0]*(j-1))%mod;

                    }
                    dp[cur][j][cost+offset][0]=
                    (dp[cur][j][cost+offset][0]+
                     (ll)dp[prv][j][cost+offset][0]*(2*j))%mod;
                    if(cost+a[i]<=2005){

                        dp[cur][j][cost+offset+a[i]][1]=
                        (dp[cur][j][cost+offset+a[i]][1]+
                         (ll)dp[prv][j][cost+offset][0]*2)%mod;
                    }

                }
                if(dp[prv][j][cost+offset][1])
                {
                    dp[cur][j+1][cost+offset-2*a[i]][1]
                    =(dp[cur][j+1][cost+offset-2*a[i]][1]+
                      (ll)dp[prv][j][cost+offset][1]*(j))%mod;
                    dp[cur][j+1][cost+offset-a[i]][2]
                    =(dp[cur][j+1][cost+offset-a[i]][2]+
                      dp[prv][j][cost+offset][1]);
                    if(dp[cur][j+1][cost+offset-a[i]][2]>=mod)
                        dp[cur][j+1][cost+offset-a[i]][2]-=mod;
                    if(j>1&&cost+2*a[i]<=2005)
                    {
                        dp[cur][j-1][cost+offset+2*a[i]][1]
                        =(dp[cur][j-1][cost+offset+2*a[i]][1]+
                        (ll)dp[prv][j][cost+offset][1]*(j-1))%mod;
                    }
                    dp[cur][j][cost+offset][1]=
                    (dp[cur][j][cost+offset][1]+
                     (ll)dp[prv][j][cost+offset][1]*(2*j-1))%mod;
                    if(cost+a[i]<=2005){
                        dp[cur][j][cost+offset+a[i]][2]=
                        (dp[cur][j][cost+offset+a[i]][2]+
                         dp[prv][j][cost+offset][1]);
                        if(dp[cur][j][cost+offset+a[i]][2]>=mod)
                            dp[cur][j][cost+offset+a[i]][2]-=mod;
                    }
                }
                if(dp[prv][j][cost+offset][2])
                {
                    if(j>1){
                        dp[cur][j+1][cost+offset-2*a[i]][2]
                        =(dp[cur][j+1][cost+offset-2*a[i]][2]+
                          (ll)dp[prv][j][cost+offset][2]*(j-1))%mod;
                        if(cost+2*a[i]<=2005){
                            dp[cur][j-1][cost+offset+2*a[i]][2]=
                            (dp[cur][j-1][cost+offset+2*a[i]][2]+
                                (ll)dp[prv][j][cost+offset][2]*(j-1)
                             )%mod;
                        }
                        dp[cur][j][cost+offset][2]=
                        (dp[cur][j][cost+offset][2]+
                         (ll)dp[prv][j][cost+offset][2]*2*(j-1))%mod;
                    }
                }
            }
        }
        cur^=1;
        sum+=a[i];
    }
    cur^=1;
    ll ans=0;
    for(int i=0;i<=l;++i)
        ans+=dp[cur][1][i+offset][2];
//    for(int i=-offset;i<0;++i)
//        assert(!dp[cur][1][i+offset][2]);
    ans%=mod;
    cout<<ans<<'\n';
}
int main()
{

    fastio;
    //build(100000);
    //brute();
    int t=1;
    //cout<<fixed<<setprecision(2);
    //cin>>t;
    for(int i=1;i<=t;i++)
    {
        solvecases(i);
        //brute(i);
    }
}
/*
4 10
3 6 2 9
8 35
3 7 1 5 10 2 11 6
*/

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