oj.uz

Submission #1099939

# Submission time Handle Problem Language Result Execution time Memory
1099939 2024-10-12T07:12:11 Z flashmt Skyscraper (JOI16_skyscraper) C++17
100 / 100
 109 ms 121396 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 121172 KB Output is correct
2 Correct 70 ms 121244 KB Output is correct
3 Correct 61 ms 121172 KB Output is correct
4 Correct 57 ms 121188 KB Output is correct
5 Correct 66 ms 121324 KB Output is correct
6 Correct 54 ms 121180 KB Output is correct
7 Correct 55 ms 121172 KB Output is correct
8 Correct 56 ms 121172 KB Output is correct
9 Correct 49 ms 121268 KB Output is correct
10 Correct 60 ms 121388 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 121164 KB Output is correct
2 Correct 59 ms 121176 KB Output is correct
3 Correct 53 ms 121172 KB Output is correct
4 Correct 54 ms 121380 KB Output is correct
5 Correct 61 ms 121224 KB Output is correct
6 Correct 51 ms 121160 KB Output is correct
7 Correct 65 ms 121172 KB Output is correct
8 Correct 68 ms 121172 KB Output is correct
9 Correct 53 ms 121284 KB Output is correct
10 Correct 49 ms 121240 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 121172 KB Output is correct
2 Correct 70 ms 121244 KB Output is correct
3 Correct 61 ms 121172 KB Output is correct
4 Correct 57 ms 121188 KB Output is correct
5 Correct 66 ms 121324 KB Output is correct
6 Correct 54 ms 121180 KB Output is correct
7 Correct 55 ms 121172 KB Output is correct
8 Correct 56 ms 121172 KB Output is correct
9 Correct 49 ms 121268 KB Output is correct
10 Correct 60 ms 121388 KB Output is correct
11 Correct 53 ms 121164 KB Output is correct
12 Correct 59 ms 121176 KB Output is correct
13 Correct 53 ms 121172 KB Output is correct
14 Correct 54 ms 121380 KB Output is correct
15 Correct 61 ms 121224 KB Output is correct
16 Correct 51 ms 121160 KB Output is correct
17 Correct 65 ms 121172 KB Output is correct
18 Correct 68 ms 121172 KB Output is correct
19 Correct 53 ms 121284 KB Output is correct
20 Correct 49 ms 121240 KB Output is correct
21 Correct 58 ms 121336 KB Output is correct
22 Correct 84 ms 121388 KB Output is correct
23 Correct 109 ms 121388 KB Output is correct
24 Correct 74 ms 121388 KB Output is correct
25 Correct 81 ms 121220 KB Output is correct
26 Correct 74 ms 121392 KB Output is correct
27 Correct 54 ms 121392 KB Output is correct
28 Correct 72 ms 121316 KB Output is correct
29 Correct 64 ms 121160 KB Output is correct
30 Correct 89 ms 121396 KB Output is correct