Submission #257879

#TimeUsernameProblemLanguageResultExecution timeMemory
257879NaimSSSkyscraper (JOI16_skyscraper)C++14
100 / 100
489 ms336004 KiB
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define td(v) v.begin(),v.end()
#define sz(v) (int)v.size()
//#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
typedef long long ll;
typedef pair<int,int> pii;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}

const int N = 103;
const int M = 1e9 + 7;

ll dp[N][1010][N][2][2];
int a[N];

int n,L;
ll solve(int i,int l,int k,int kl,int kr){
    // tem k componentes, kl-> se tem algum no left , kr ->tem no right
    if(k < 0)return 0;
    
    if(i)l+= (a[i] - a[i-1])*(2*k + kl + kr);

    if(l > L)return 0;

    if(i == n - 1){
        return !k;
    }

    ll &x = dp[i][l][k][kl][kr];
    if(x!=-1)return x;
    x=0;

    // create to left:
    // append to left
    x += solve(i+1,l,k,1,kr); 
    // append + merge
    x += solve(i+1,l,k-1,1,kr) * k;

    // create to right:
    // append only
    x += solve(i+1,l,k,kl,1);
    // append + merge
    x += solve(i+1,l,k-1,kl,1) * k;

    // now the middle stuff    

    // isolado
    x += solve(i+1,l,k+1,kl,kr);

    // merge with one ( to the left/right of it)
    x += 2ll*k*solve(i+1,l,k,kl,kr);

    // merge two boys
    x += 1ll * k * (k-1) * solve(i+1,l,k-1,kl,kr);

    x%=M;
    return x;
}


int32_t main(){
  fastio;
  cin >> n >> L;

  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  sort(a,a+n);

  ms(dp,-1);

  cout << solve(0,0,0,0,0) << endl; 

  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
  
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...