제출 #316561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
316561		LifeHappen__	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	553 ms	362876 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define forinc(a,b,c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a,b,c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a,b) for(auto &a:b)
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ar array
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

const int N=105;
const int mod=1e9+7;
int n,a[N],b[N],L;
int f[N][N][2][2][N*10];

void add(int &x,int y){
   x=(x+y)%mod;
}

int dfs(int i,int cnt,int lef,int rig,int val){
   if(i) val+=a[i-1]*(2*cnt-lef-rig);
   if(val>L) return 0;
   int &ans=f[i][cnt][lef][rig][val];
   if(ans!=-1) return ans;
   if(i==n) return !(val>L||cnt!=1||!lef||!rig);
   ans=0;
   ///new comp
   add(ans,dfs(i+1,cnt+1,lef,rig,val)*(cnt+1-lef-rig)%mod);
   if(!lef) add(ans,dfs(i+1,cnt+1,1,rig,val));
   if(!rig) add(ans,dfs(i+1,cnt+1,lef,1,val));
   if(cnt){
      if(cnt>=2) add(ans,dfs(i+1,cnt-1,lef,rig,val)*(cnt-1)%mod);
      add(ans,dfs(i+1,cnt,lef,rig,val)*(cnt-lef)%mod);
      add(ans,dfs(i+1,cnt,lef,rig,val)*(cnt-rig)%mod);
      if(!lef) add(ans,dfs(i+1,cnt,1,rig,val));
      if(!rig) add(ans,dfs(i+1,cnt,lef,1,val));
   }
   return ans;
}

int32_t main(){
   fasty;

   cin>>n>>L;
   if(n==1) return cout<<1,0;
   forinc(i,0,n-1) cin>>b[i];
   sort(b, b+n);
   forinc(i,0,n-1) a[i]=b[i+1]-b[i];
   reset(f,-1);
   cout<<dfs(0,0,0,0,0);
}

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