Submission #623670

#	Time	Username	Problem	Language	Result	Execution time	Memory
623670		rrrr10000	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	230 ms	5972 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pb emplace_back
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;
const ll mod=1000000007;

ll solve(ll n,ll L,vi v){
    vvvi dp(3,vvi(n+1,vi(L+1)));
    dp[0][1][0]=1;dp[1][1][0]=2;dp[2][1][0]=1;
    REP(i,1,n){
        vvvi ndp(3,vvi(n+1,vi(L+1)));
        rep(j,3)REP(k,1,n+1)rep(l,L+1)if(dp[j][k][l]&&l+(k*2-j)*(v[i]-v[i-1])<=L&&k*2-j>0)ndp[j][k][l+(k*2-j)*(v[i]-v[i-1])]+=dp[j][k][l];
        rep(j,3)REP(k,1,n+1)rep(l,L+1)dp[j][k][l]=ndp[j][k][l]%mod;
        rep(j,3)REP(k,1,n+1)rep(l,L+1)ndp[j][k][l]=0;
        rep(j,3)REP(k,1,n+1)rep(l,L+1)if(dp[j][k][l]){
            if(k>1)ndp[j][k-1][l]+=dp[j][k][l]*(k-1)%mod;
            if(j<2)ndp[j+1][k][l]+=dp[j][k][l]*(2-j)%mod;
            ndp[j][k][l]+=dp[j][k][l]*(2*k-j)%mod;
            ndp[j][k+1][l]+=dp[j][k][l]*(k+1-j)%mod;
            if(j<2)ndp[j+1][k+1][l]+=dp[j][k][l]*(2-j)%mod;
        }
        rep(j,3)REP(k,1,n+1)rep(l,L+1){
            dp[j][k][l]=ndp[j][k][l]%mod;
            // if(dp[j][k][l])cout<<j<<' '<<k<<' '<<l<<' '<<dp[j][k][l]<<endl;
        }
    }
    ll ans=0;
    rep(i,L+1)ans+=dp[2][1][i];
    return ans%mod;
}
int main(){
    ll n,L;cin>>n>>L;
    vi v(n);
    rep(i,n)cin>>v[i];
    sort(all(v));
    out(solve(n,L,v));
}

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