oj.uz

Submission #659530

# Submission time Handle Problem Language Result Execution time Memory
659530 2022-11-18T11:40:04 Z tibinyte Magneti (COCI21_magneti) C++14
110 / 110
 580 ms 113980 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 113980 KB Output is correct
2 Correct 67 ms 12548 KB Output is correct
3 Correct 85 ms 16708 KB Output is correct
4 Correct 67 ms 12916 KB Output is correct
5 Correct 92 ms 17548 KB Output is correct
6 Correct 208 ms 41980 KB Output is correct
7 Correct 203 ms 62688 KB Output is correct
8 Correct 65 ms 12068 KB Output is correct
9 Correct 108 ms 36216 KB Output is correct
10 Correct 63 ms 12040 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 16764 KB Output is correct
2 Correct 65 ms 12300 KB Output is correct
3 Correct 84 ms 16788 KB Output is correct
4 Correct 66 ms 12680 KB Output is correct
5 Correct 83 ms 16788 KB Output is correct
6 Correct 66 ms 12800 KB Output is correct
7 Correct 82 ms 16788 KB Output is correct
8 Correct 65 ms 12408 KB Output is correct
9 Correct 65 ms 12680 KB Output is correct
10 Correct 65 ms 12020 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 13064 KB Output is correct
2 Correct 65 ms 12420 KB Output is correct
3 Correct 69 ms 13072 KB Output is correct
4 Correct 67 ms 12544 KB Output is correct
5 Correct 71 ms 13060 KB Output is correct
6 Correct 64 ms 12156 KB Output is correct
7 Correct 69 ms 13260 KB Output is correct
8 Correct 64 ms 12148 KB Output is correct
9 Correct 64 ms 12408 KB Output is correct
10 Correct 64 ms 12164 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 113980 KB Output is correct
2 Correct 67 ms 12548 KB Output is correct
3 Correct 85 ms 16708 KB Output is correct
4 Correct 67 ms 12916 KB Output is correct
5 Correct 92 ms 17548 KB Output is correct
6 Correct 208 ms 41980 KB Output is correct
7 Correct 203 ms 62688 KB Output is correct
8 Correct 65 ms 12068 KB Output is correct
9 Correct 108 ms 36216 KB Output is correct
10 Correct 63 ms 12040 KB Output is correct
11 Correct 87 ms 16764 KB Output is correct
12 Correct 65 ms 12300 KB Output is correct
13 Correct 84 ms 16788 KB Output is correct
14 Correct 66 ms 12680 KB Output is correct
15 Correct 83 ms 16788 KB Output is correct
16 Correct 66 ms 12800 KB Output is correct
17 Correct 82 ms 16788 KB Output is correct
18 Correct 65 ms 12408 KB Output is correct
19 Correct 65 ms 12680 KB Output is correct
20 Correct 65 ms 12020 KB Output is correct
21 Correct 69 ms 13064 KB Output is correct
22 Correct 65 ms 12420 KB Output is correct
23 Correct 69 ms 13072 KB Output is correct
24 Correct 67 ms 12544 KB Output is correct
25 Correct 71 ms 13060 KB Output is correct
26 Correct 64 ms 12156 KB Output is correct
27 Correct 69 ms 13260 KB Output is correct
28 Correct 64 ms 12148 KB Output is correct
29 Correct 64 ms 12408 KB Output is correct
30 Correct 64 ms 12164 KB Output is correct
31 Correct 577 ms 113868 KB Output is correct
32 Correct 383 ms 74060 KB Output is correct
33 Correct 578 ms 113864 KB Output is correct
34 Correct 167 ms 33004 KB Output is correct
35 Correct 571 ms 113868 KB Output is correct
36 Correct 93 ms 18044 KB Output is correct
37 Correct 580 ms 113928 KB Output is correct
38 Correct 154 ms 28212 KB Output is correct
39 Correct 567 ms 113920 KB Output is correct
40 Correct 211 ms 42504 KB Output is correct
41 Correct 560 ms 113864 KB Output is correct
42 Correct 66 ms 12680 KB Output is correct
43 Correct 561 ms 113864 KB Output is correct
44 Correct 109 ms 22280 KB Output is correct
45 Correct 559 ms 113872 KB Output is correct
46 Correct 65 ms 12364 KB Output is correct
47 Correct 132 ms 42380 KB Output is correct
48 Correct 96 ms 25548 KB Output is correct
49 Correct 68 ms 14076 KB Output is correct
50 Correct 65 ms 12180 KB Output is correct