oj.uz

Submission #850258

# Submission time Handle Problem Language Result Execution time Memory
850258 2023-09-16T08:37:05 Z serifefedartar Magneti (COCI21_magneti) C++14
0 / 110
 1000 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 12000;

ll fact[MAXN], inv[MAXN];
ll expo(ll a, ll b) {
    ll res = 1;
    while (b) { 
        if (b & 1) 
            res = (res * a) % MOD;
        a = (a * a) % MOD;
        b /= 2;
    }
    return res;
}

ll nCr(ll n, ll r) {
    if (r > n)
        return 0LL;
    return ((fact[n] * inv[r] % MOD) * inv[n-r]) % MOD;
}

ll dist(ll item, ll place) {
    return nCr(item + place - 1, item);
}

vector<ll> seq;
int main() {
    fast
    fact[0] = inv[0] = 1;
    for (ll i = 1; i < MAXN; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
        inv[i] = expo(fact[i], MOD - 2);
    }
    
    ll N, L;
    cin >> N >> L;

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

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

    ll ans = 0;
    for (int l = 1; l <= L; l++) {
        for (int r = l + 1; r <= L; r++) {
            for (int l_seq = 0; l_seq < N; l_seq++) {
                for (int r_seq = 0; r_seq < N; r_seq++) {
                    if (l_seq == r_seq)
                        continue;
                    ll left_border = l + seq[l_seq];
                    ll right_border = r - seq[r_seq];
                    ll open = right_border - left_border + 1;
                    ll sum_rem = 2*(sum - seq[l_seq] - seq[r_seq]) - N + 2;
                    ll rem = open - sum_rem;

                    if (rem < 0)
                        continue;
                    ll res = (fact[N-2] * dist(rem, N-1)) % MOD;
                    ans = (ans + res) % MOD; 
                }
            }
        }
    }
    cout << ans << "\n";
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

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