Submission #836464

#	Time	Username	Problem	Language	Result	Execution time	Memory
836464		lipa_debowa	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	46 ms	5332 KiB

skyscraper

// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
// tree_order_statistics_node_update> ordered_set;

#define rep(i, n) for (int i = 0; i < n; i++)
#define pb push_back
#define debug(x) cout << #x << " " << x << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vll vector<ll>
#define vvll vector<vll>
#define ld long double
#define ull unsigned long long
#define vull vector<ull>
#define fi first
#define se second
#define PII pair<int, int>
#define vPII vector<PII>
#define getunique(v)                                                           \
  {                                                                            \
    sort(v.begin(), v.end());                                                  \
    v.erase(unique(v.begin(), v.end()), v.end());                              \
  }
#define int128 __int128
#define LSOne(x) (x & (-x))

const ll mod = 1e9 + 7;

namespace modop {

ll madd(long long a, long long b) {
  return (a + b) % mod;
}

ll msub(ll a, ll b) {
  return (((a - b) % mod) + mod) % mod;
}

ll mmul(ll a, ll b) {
  return ((a % mod) * (b % mod)) % mod;
}

ll mpow(ll base, ll exp) {
  ll res = 1;
  while (exp) {
    if (exp % 2 == 1) {
      res = (res * base) % mod;
    }
    exp >>= 1;
    base = (base * base) % mod;
  }
  return res;
}

ll minv(ll base) {
  return mpow(base, mod - 2);
}

ll mdiv(ll a, ll b) {
  return mmul(a, minv(b));
}

const ll FACTORIAL_SIZE = 1.1e6;
ll fact[FACTORIAL_SIZE], ifact[FACTORIAL_SIZE];
bool __factorials_generated__ = 0;

void gen_factorial(ll n) {
  __factorials_generated__ = 1;
  fact[0] = fact[1] = ifact[0] = ifact[1] = 1;

  for (ll i = 2; i <= n; i++) {
    fact[i] = (i * fact[i - 1]) % mod;
  }
  ifact[n] = minv(fact[n]);
  for (ll i = n - 1; i >= 2; i--) {
    ifact[i] = ((i + 1) * ifact[i + 1]) % mod;
  }
}

ll nck(ll n, ll k) {
  if (!__factorials_generated__) {
    cerr << "Call gen_factorial you dope" << endl;
    exit(1);
  }
  if (k < 0 || n < k)
    return 0;
  ll den = (ifact[k] * ifact[n - k]) % mod;
  return (den * fact[n]) % mod;
}

} // namespace modop

using namespace modop;

ll dp[2][105][3][1005];

void solve([[maybe_unused]] int tc_idx = 0) {
  int n,L; cin >> n >> L;
  vi a(n+1); rep(i,n) cin >> a[i+1];
  if(n==1){
    cout << 1;
    return;
  }
  sort(all(a));
  a[0] = a[1];
  a.pb(a[n]);
  dp[0][0][0][0] = 1;
  for(int i = 1; i <= n; i++){
    int cur = i&1;
    int pre = cur^1;
    memset(dp[cur],0,sizeof(dp[cur]));
    for(int j = 1; j <= i; j++){
      for(int k = 0; k <= 2; k++){
        for(int l = 0; l <= L; l++){
          // brzegow jest j * 2 - k
          int pom = l-(2*j-k)*(a[i+1]-a[i]);
          if(pom >= 0){
            // tworzymy nowy nie na koncu
            if(j) dp[cur][j][k][l] += dp[pre][j-1][k][pom]*(j-k);
            // tworzymy nowy na koncu
            if(j and k) dp[cur][j][k][l] += dp[pre][j-1][k-1][pom]*(3-k);
            // dołaczamy z jednej storny (nie na koncach)
            dp[cur][j][k][l] += dp[pre][j][k][pom]*(2*j-k);
            // dolaczany na koncu ktoryms
            if(k) dp[cur][j][k][l] += dp[pre][j][k-1][pom]*(3-k);
            // laczymy dwa
            dp[cur][j][k][l] += dp[pre][j+1][k][pom] * j;

            dp[cur][j][k][l] %= mod;
          }
        }
      }
    }
  }
  ll suma = 0;
  rep(i,L+1) suma = madd(suma, dp[n&1][1][2][i]);
  cout << suma;
}


int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cout << setprecision(16) << fixed;
  // srand(time(NULL));
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  int tt = 1;
  // cin >> tt;
  rep(i, tt) solve(i);
}

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