oj.uz

Submission #588459

# Submission time Handle Problem Language Result Execution time Memory
588459 2022-07-03T10:29:13 Z MilosMilutinovic Magneti (COCI21_magneti) C++14
110 / 110
 300 ms 4440 KB 
/**
 *    author:  wxhtzdy
 *    created: 03.07.2022 12:01:33
**/
#include <bits/stdc++.h>

using namespace std;
 
string to_string(string s) {
  return '"' + s + '"';
}
string to_string(const char* s) {
  return to_string((string) s);
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(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())); }
  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 U>
  friend std::istream& operator>>(std::istream& 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>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::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 = 1e9 + 7;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);
 
Mint C(int n, int k) {
  if (k < 0 || k > n) {
    return 0;
  }
  while ((int) fact.size() < n + 1) {
    fact.push_back(fact.back() * (int) fact.size());
    inv_fact.push_back(1 / fact.back());
  }
  return fact[n] * inv_fact[k] * inv_fact[n - k];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, l;
  cin >> n >> l;
  vector<int> r(n);
  for (int i = 0; i < n; i++) {
    cin >> r[i];
    --r[i];
  }
  sort(r.begin(), r.end());
  vector<vector<Mint>> dp(n + 1, vector<Mint>(l + 1));                                                            
  dp[0][0] = 1;
  for (int i = 0; i < n; i++) {
    vector<vector<Mint>> new_dp(n + 1, vector<Mint>(l + 1));
    for (int j = 0; j <= n; j++) {
      for (int x = 0; x <= l; x++) {
        {
          // new component
          if (j > 0) {
            new_dp[j][x] += dp[j - 1][x] * j;
          }
        }
        {
          // merge with one
          int prv_x = x - r[i]; 
          if (prv_x >= 0) {
            new_dp[j][x] += dp[j][prv_x] * (2 * j); 
          }
        }
        {
          // merge with two
          int prv_j = j + 1;
          int prv_x = x - 2 * r[i]; 
          if (prv_j <= n && prv_x >= 0) {
            new_dp[j][x] += dp[prv_j][prv_x] * j; 
          }
        }
      }   
    }
    swap(dp, new_dp);
  }
  Mint ans = 0;                 
  for (int i = 0; i <= l; i++) {
    ans += dp[1][i] * C(l - i, n); 
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 4360 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 13 ms 1048 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 17 ms 764 KB Output is correct
6 Correct 90 ms 2368 KB Output is correct
7 Correct 74 ms 2404 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 28 ms 1652 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1220 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 12 ms 1220 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 14 ms 1208 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 14 ms 1200 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 4360 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 13 ms 1048 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 17 ms 764 KB Output is correct
6 Correct 90 ms 2368 KB Output is correct
7 Correct 74 ms 2404 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 28 ms 1652 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 13 ms 1220 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 12 ms 1220 KB Output is correct
14 Correct 3 ms 572 KB Output is correct
15 Correct 14 ms 1208 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 14 ms 1200 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 3 ms 340 KB Output is correct
22 Correct 1 ms 356 KB Output is correct
23 Correct 4 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 4 ms 340 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 283 ms 4440 KB Output is correct
32 Correct 172 ms 2984 KB Output is correct
33 Correct 297 ms 4344 KB Output is correct
34 Correct 61 ms 1860 KB Output is correct
35 Correct 278 ms 4324 KB Output is correct
36 Correct 16 ms 1136 KB Output is correct
37 Correct 296 ms 4332 KB Output is correct
38 Correct 48 ms 1124 KB Output is correct
39 Correct 275 ms 4340 KB Output is correct
40 Correct 83 ms 2476 KB Output is correct
41 Correct 300 ms 4412 KB Output is correct
42 Correct 2 ms 468 KB Output is correct
43 Correct 266 ms 4356 KB Output is correct
44 Correct 27 ms 1376 KB Output is correct
45 Correct 287 ms 4328 KB Output is correct
46 Correct 2 ms 596 KB Output is correct
47 Correct 48 ms 2348 KB Output is correct
48 Correct 21 ms 1076 KB Output is correct
49 Correct 4 ms 852 KB Output is correct
50 Correct 1 ms 340 KB Output is correct