oj.uz

Submission #659524

# Submission time Handle Problem Language Result Execution time Memory
659524 2022-11-18T11:19:48 Z tibinyte Magneti (COCI21_magneti) C++14
20 / 110
 1000 ms 12168 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);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        p[i] = i;
    }
    modint ans = 0;
    do
    {
        vector<int> b(n + 1);
        for (int i = 1; i <= n; ++i)
        {
            b[i] = a[p[i]];
        }
        int sum = 1;
        for (int i = 2; i <= n; ++i)
        {
            sum += max(b[i], b[i - 1]);
        }
        ans += C.sb(l - sum, n + 1);
    } while (next_permutation(p.begin() + 1, p.end()));
    cout << ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 12048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 12168 KB Output is correct
2 Correct 65 ms 12056 KB Output is correct
3 Correct 256 ms 12036 KB Output is correct
4 Correct 63 ms 12024 KB Output is correct
5 Correct 224 ms 12040 KB Output is correct
6 Correct 63 ms 11988 KB Output is correct
7 Correct 218 ms 12036 KB Output is correct
8 Correct 222 ms 11988 KB Output is correct
9 Correct 63 ms 12032 KB Output is correct
10 Correct 62 ms 12024 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 12024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 12048 KB Time limit exceeded
2 Halted 0 ms 0 KB -