oj.uz

답안 #1008917

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008917 2024-06-27T05:15:50 Z nima_aryan Skyscraper (JOI16_skyscraper) C++17
20 / 100
 2000 ms 77440 KB 
/**
 *    author:  NimaAryan
 *    created: 2024-06-26 20:39:48
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;

  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }

  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }

  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) { Modular result(*this); *this += 1; return result; }
  Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
  Modular operator-() const { return Modular(-value); }

  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type & operator*=(const Modular& rhs) {
#ifdef _WIN32
    uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
    asm(
      "divl %4; \n\t"
      : "=a" (d), "=d" (m)
      : "d" (xh), "a" (xl), "r" (mod())
    );
    value = m;
#else
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type & operator*=(const Modular& rhs) {
    long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if < !is_integral<typename Modular<U>::Type>::value, Modular >::type & operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }

  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

  friend const Type& abs(const Modular& x) { return x.value; }

  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);

 private:
  Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
template <typename T, typename U> Modular<T> operator^(const Modular<T>& lhs, U rhs) { return power(lhs, rhs); };

template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}

template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}

// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}

// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}

/*
using ModType = int;

struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/

constexpr int md = (int) 1e9 + 7;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, L;
  cin >> N >> L;

  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }

  if (N == 1) {
    cout << 1 << "\n";
    return 0;
  }

  sort(A.begin(), A.end());
  int M = max(accumulate(A.begin(), A.end(), 0) / 2 + 100, 2 * A[0] + 5);
  int T = M + 1 + L;
  vector f(3, vector(N + 1, vector<Mint>(T + 1)));
  f[0][1][0] = 1;
  f[1][1][-A[0] + M] = 2;
  f[2][1][2 * -A[0] + M] = 1;
  for (int i = 1; i < N; ++i) {
    vector g(3, vector(N + 1, vector<Mint>(T + 1)));
    for (int c = 1; c <= N; ++c) {
      for (int s = 0; s <= T; ++s) {
        {
          if (c + 1 <= N && s - 2 * A[i] >= 0) {
            g[0][c + 1][s - 2 * A[i]] += f[0][c][s] * max(0, c - 1);
          }
          g[0][c][s] += f[0][c][s] * max(0, 2 * c - 2);
          if (c - 1 >= 0 && s + 2 * A[i] <= T) {
            g[0][c - 1][s + 2 * A[i]] += f[0][c][s] * max(0, c - 1);
          }
        }
        {
          if (c + 1 <= N && s - 2 * A[i] >= 0) {
            g[1][c + 1][s - 2 * A[i]] += f[1][c][s] * c;
          }
          if (c + 1 <= N && s - A[i] >= 0) {
            g[0][c + 1][s - A[i]] += f[1][c][s];
          }
          g[1][c][s] += f[1][c][s] * max(0, 2 * c - 1);
          if (s + A[i] <= T) {
            g[0][c][s + A[i]] += f[1][c][s];
          }
          if (c - 1 >= 0 && s + 2 * A[i] <= T) {
            g[1][c - 1][s + 2 * A[i]] += f[1][c][s] * max(0, c - 1);
          }
        }
        {
          if (c + 1 <= N && s - 2 * A[i] >= 0) {
            g[2][c + 1][s - 2 * A[i]] += f[2][c][s] * (c + 1);
          }
          if (c + 1 <= N && s - A[i] >= 0) {
            g[1][c + 1][s - A[i]] += f[2][c][s] * 2;
          }
          g[2][c][s] += f[2][c][s] * 2 * c;
          if (s + A[i] <= T) {
            g[1][c][s + A[i]] += f[2][c][s] * 2;
          }
          if (c - 1 >= 0 && s + 2 * A[i] <= T) {
            g[2][c - 1][s + 2 * A[i]] += f[2][c][s] * max(0, c - 1);
          }
        }
      }
    }
    f.swap(g);
  }

  Mint ans = 0;
  for (int l = 0; l <= L; ++l) {
    ans += f[0][1][l + M];
  }
  cout << ans << "\n";

  return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 676 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 604 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 676 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 22 ms 856 KB Output is correct
22 Correct 431 ms 6472 KB Output is correct
23 Execution timed out 2070 ms 77440 KB Time limit exceeded
24 Halted 0 ms 0 KB -