QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276933#7875. Queue SortingsupepapupuWA 4ms5576kbC++171.8kb2023-12-06 13:17:472023-12-06 13:17:48

Judging History

This is the latest submission verdict.

  • [2023-12-06 13:17:48]
  • Judged
  • Verdict: WA
  • Time: 4ms
  • Memory: 5576kb
  • [2023-12-06 13:17:47]
  • Submitted

answer

#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
#define debug(x) cout << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 3e5 + 10, INF = 0x3f3f3f3f, mod = 998244353;

void inc(ll &a, ll b) {
    a += b;
    if (a >= mod) a -= mod;
}
void dec(ll &a, ll b) {
    a -= b;
    if (a < 0) a += mod;
}
ll add(ll a, ll b) {
    a += b;
    return a >= mod ? a - mod : a;
}
ll del(ll a, ll b) {
    a -= b;
    return a < 0 ? a + mod : a;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int m = accumulate(a.begin(), a.end(), 0);
    vector<vector<ll>> binom(m + 1, vector<ll>(m + 1));
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (!j) binom[i][j] = 1;
            else binom[i][j] = add(binom[i - 1][j], binom[i - 1][j - 1]);
        }
    }
    vector<ll> f;
    for (int i = 1, s = 0; i <= n; ++i) {
        if (!a[i]) continue;
        vector<ll> dp(s + a[i] + 1);
        for (int j = a[i]; j < s + a[i]; ++j) {
            dp[j] = 1;
            if (a[i] > 1) ++dp[s + a[i]];
        }
        for (int j = 1; j <= s; ++j) {
            // debug(j);
            for (int k = j + a[i]; k < s + a[i]; ++k) {
                inc(dp[k], f[j]);
                // debug(f[j] * binom[k - j - 1][a[i] - 1]);
            }
            // dec(dp[s + a[i]], f[j]);
            inc(dp[j], f[j]);
        }
        s += a[i];
        f.swap(dp);
        // for (int i: f) cout << i << ' '; cout << el;
    }
    ll ans = 1;
    for (ll i: f) inc(ans, i);
    cout << ans << el;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3552kb

input:

4
1 1 1 1

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: -100
Wrong Answer
time: 4ms
memory: 5576kb

input:

300
0 5 2 2 1 0 3 2 2 5 2 1 1 2 1 3 2 3 2 0 0 0 0 1 2 2 3 0 2 2 3 2 0 2 3 0 6 0 0 2 0 1 3 2 1 1 1 3 4 0 1 0 4 1 1 1 1 1 1 2 3 2 1 2 3 2 3 0 5 3 3 2 0 1 1 0 2 1 1 2 0 0 2 1 1 3 2 2 1 2 1 3 0 3 0 1 2 2 0 5 0 2 2 0 0 0 1 2 1 4 2 1 1 0 3 0 2 0 3 1 1 2 0 2 1 1 0 2 0 1 2 2 3 3 1 1 1 1 0 1 3 3 1 0 2 2 4 2 ...

output:

896393542

result:

wrong answer 1st numbers differ - expected: '507010274', found: '896393542'