QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276933 | #7875. Queue Sorting | supepapupu | WA | 4ms | 5576kb | C++17 | 1.8kb | 2023-12-06 13:17:47 | 2023-12-06 13:17:48 |
Judging History
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'