Submission #659530

#	Time	Username	Problem	Language	Result	Execution time	Memory
659530		tibinyte	Magneti (COCI21_magneti)	C++14	110 / 110	580 ms	113980 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int32_t MOD = 1e9 + 7;
struct modint
{
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_ % MOD) {}
    modint(int64_t value_) : value(value_ % MOD) {}
    inline modint operator+(modint other) const
    {
        int32_t c = this->value + other.value;
        return modint(c >= MOD ? c - MOD : c);
    }
    inline modint operator-(modint other) const
    {
        int32_t c = this->value - other.value;
        return modint(c < 0 ? c + MOD : c);
    }
    inline modint operator*(modint other) const
    {
        int32_t c = (int64_t)this->value * other.value % MOD;
        return modint(c < 0 ? c + MOD : c);
    }
    inline modint &operator+=(modint other)
    {
        this->value += other.value;
        if (this->value >= MOD)
            this->value -= MOD;
        return *this;
    }
    inline modint &operator-=(modint other)
    {
        this->value -= other.value;
        if (this->value < 0)
            this->value += MOD;
        return *this;
    }
    inline modint &operator*=(modint other)
    {
        this->value = (int64_t)this->value * other.value % MOD;
        if (this->value < 0)
            this->value += MOD;
        return *this;
    }
    inline modint operator-() const { return modint(this->value ? MOD - this->value : 0); }
    modint pow(int32_t k) const
    {
        modint x = *this, y = 1;
        for (; k; k >>= 1)
        {
            if (k & 1)
                y *= x;
            x *= x;
        }
        return y;
    }
    modint inv() const { return pow(MOD - 2); } // MOD must be a prime
    inline modint operator/(modint other) const { return *this * other.inv(); }
    inline modint operator/=(modint other) { return *this *= other.inv(); }
    inline bool operator==(modint other) const { return value == other.value; }
    inline bool operator!=(modint other) const { return value != other.value; }
    inline bool operator<(modint other) const { return value < other.value; }
    inline bool operator>(modint other) const { return value > other.value; }
};
modint operator*(int64_t value, modint n) { return modint(value) * n; }
modint operator*(int32_t value, modint n) { return modint(value) * n; }
istream &operator>>(istream &in, modint &n) { return in >> n.value; }
ostream &operator<<(ostream &out, modint n) { return out << n.value; }
struct combi
{
    int n;
    vector<modint> facts, finvs, invs;
    combi(int _n) : n(_n), facts(_n), finvs(_n), invs(_n)
    {
        facts[0] = finvs[0] = 1;
        invs[1] = 1;
        for (int i = 2; i < n; i++)
            invs[i] = invs[MOD % i] * (-MOD / i);
        for (int i = 1; i < n; i++)
        {
            facts[i] = facts[i - 1] * i;
            finvs[i] = finvs[i - 1] * invs[i];
        }
    }
    inline modint fact(int n) { return facts[n]; }
    inline modint finv(int n) { return finvs[n]; }
    inline modint inv(int n) { return invs[n]; }
    inline modint ncr(int n, int k) { return n < k or k < 0 ? 0 : facts[n] * finvs[k] * finvs[n - k]; }
    inline modint aranj(int n, int k) { return ncr(n, k) * facts[k]; }
    inline modint sb(int n, int k) { return ncr(n + k - 1, n); };
};
combi C(1e6 + 1);
int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, l;
    cin >> n >> l;
    vector<int> a(n + 1);
    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    sort(a.begin() + 1, a.end());
    modint dp[n + 1][n + 1][l + 1];
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= n; ++j)
        {
            for (int t = 0; t <= l; ++t)
            {
                dp[i][j][t] = 0;
            }
        }
    }
    dp[1][1][0] = 1;
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            for (int s = 0; s <= l; ++s)
            {
                // make new component
                dp[i][j][s] += dp[i - 1][j - 1][s] * j;

                // push left
                if (s >= a[i])
                {
                    dp[i][j][s] += dp[i - 1][j][s - a[i]] * j;
                }

                // push right
                if (s >= a[i])
                {
                    dp[i][j][s] += dp[i - 1][j][s - a[i]] * j;
                }

                // merge
                if (s >= 2 * a[i])
                {
                    dp[i][j][s] += dp[i - 1][j + 1][s - 2 * a[i]] * j;
                }
            }
        }
    }
    modint ans = 0;
    for (int i = 0; i <= l; ++i)
    {
        ans += dp[n][1][i] * C.sb(l - i - 1, n + 1);
    }
    cout << ans;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:100:9: warning: unused variable 'sum' [-Wunused-variable]
  100 |     int sum = 0;
      |         ^~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50