Submission #1099939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099939		flashmt	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	109 ms	121396 KiB

skyscraper

#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
template<int MOD_> struct modnum {
  static constexpr int MOD = MOD_;
  static_assert(MOD_ > 0, "MOD must be positive");

private:
  using ll = long long;

  int v;

  static int minv(int a, int m) {
    a %= m;
    assert(a);
    return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  }

public:

  modnum() : v(0) {}
  modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  explicit operator int() const { return v; }
  friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }

  friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

  modnum inv() const {
    modnum res;
    res.v = minv(v, MOD);
    return res;
  }
  friend modnum inv(const modnum& m) { return m.inv(); }
  modnum neg() const {
    modnum res;
    res.v = v ? MOD-v : 0;
    return res;
  }
  friend modnum neg(const modnum& m) { return m.neg(); }

  modnum operator- () const {
    return neg();
  }
  modnum operator+ () const {
    return modnum(*this);
  }

  modnum& operator ++ () {
    v ++;
    if (v == MOD) v = 0;
    return *this;
  }
  modnum& operator -- () {
    if (v == 0) v = MOD;
    v --;
    return *this;
  }
  modnum& operator += (const modnum& o) {
    v += o.v;
    if (v >= MOD) v -= MOD;
    return *this;
  }
  modnum& operator -= (const modnum& o) {
    v -= o.v;
    if (v < 0) v += MOD;
    return *this;
  }
  modnum& operator *= (const modnum& o) {
    v = int(ll(v) * ll(o.v) % MOD);
    return *this;
  }
  modnum& operator /= (const modnum& o) {
    return *this *= o.inv();
  }

  friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

template<typename T> T pow(T a, long long b) {
  assert(b >= 0);
  T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
}

template<int M> string to_string(modnum<M> x) {
  return to_string(int(x));
}

using num = modnum<int(1e9) + 7>;

const int N = 101;
const int L = 1010;
const int oo = 1 << 20;

num f[N][N][L][3];

int main()
{
  int n, l;
  cin >> n >> l;
  if (n == 1)
  {
    cout << 1 << endl;
    return 0;
  }
  vector<int> a(n);
  for (int &x : a)
    cin >> x;
  sort(begin(a), end(a));
  a.push_back(oo);

  if ((a[1] - a[0]) * 2 <= l)
    f[0][1][(a[1] - a[0]) * 2][0] = 1;
  if (a[1] - a[0] <= l)
    f[0][1][a[1] - a[0]][1] = 2;

  auto update = [&](int i, int j, int s, int ends, num curF)
  {
    if (s <= l)
      f[i][j][s][ends] += curF;
  };

  for (int i = 1; i < n; i++)
    for (int j = 1; j <= i; j++)
      for (int s = 0; s <= l; s++)
        for (int ends = 0; ends < 3; ends++)
        {
          num curF = f[i - 1][j][s][ends];
          if (!int(curF))
            continue;

          int diff = a[i + 1] - a[i];

          // put at ends
          if (ends < 2)
          {
            update(i, j + 1, s + diff * (j * 2 - ends + 1), ends + 1, curF * (2 - ends));
            update(i, j, s + diff * (j * 2 - ends - 1), ends + 1, curF * (2 - ends));
          }

          // mid
          update(i, j + 1, s + diff * (j * 2 - ends + 2), ends, curF * (j + 1 - ends));
          update(i, j, s + diff * (j * 2 - ends), ends, curF * (j * 2 - ends));
          if (j > 1)
            update(i, j - 1, s + diff * (j * 2 - ends - 2), ends, curF * (j - 1));
        }

  num ans;
  for (int s = 0; s <= l; s++)
    ans += f[n - 1][1][s][2];
  cout << ans << endl;
}

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