Submission #257880

#	Time	Username	Problem	Language	Result	Execution time	Memory
257880		NaimSS	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	305 ms	252152 KiB

skyscraper

#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][3];
int a[N];

int n,L;
ll solve(int i,int l,int k,int t){
    // tem k componentes, tem t pontas
    if(k < 0)return 0;
    
    if(i)l+= (a[i] - a[i-1])*(2*k + t);

    if(l > L)return 0;

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

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

    // coisa das pontas
    
    if(t == 0){
      // pode criar qq um dos dois lados
      x += 2ll * solve(i+1,l,k,1);
      x += 2ll * k * solve(i+1,l,k-1,1); // cria e ja da merge
    }
    if(t == 1){
      // no lado q ja tem
      x += solve(i+1,l,k,1);
      x += 1ll * k * solve(i+1,l,k-1,1);

      // cria um novo
      x += 1ll * solve(i+1,l,k,2);
      x += 1ll * k * solve(i+1,l,k-1,2);
    }
    if(t == 2){
      // so junta ou dá merge com qq um dos lados
      x += 2ll *solve(i+1,l,k,t) + 2ll * k * solve(i+1,l,k-1,t);
    }

    // now the middle stuff    

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

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

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

    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) << endl; 

  // math -> gcd it all
  // Did u check N=1? Did you switch N,M?
  
}

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