QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#283395 | #7875. Queue Sorting | wxy | WA | 12ms | 4508kb | C++14 | 1.3kb | 2023-12-14 16:11:28 | 2023-12-14 16:11:28 |
Judging History
answer
// start time : 16 : 05
#include <bits/stdc++.h>
#define rep(i,l,r) for (int i = l; i <= r; i++)
#define per(i,r,l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define pb push_back
#define mp std::make_pair
#define gin std::cin
#define prt std::cout
#define edl std::endl
namespace Main {
const int N = 505,mod = 998244353;
int n,a[N],f[N][N],c[N][N];
void add(int &x,int v) {
x += v; x %= mod;
}
void main() {
scanf("%d",&n);
c[0][0] = 1;
rep(i,1,n) {
c[i][0] = c[i][i] = 1;
rep(j,1,i - 1) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
rep(i,1,n) {
scanf("%d",&a[i]);
}
f[n + 1][n + 1] = 1;
int sum = 0;
per(i,n + 1,2) {
sum += a[i];
rep(j,1,n + 1) {
rep(k,0,a[i - 1]) {
if (sum + k > n - j + 1) continue;
if (k != a[i - 1]) {
rep(t,1,j - 1) {
if (j - t >= a[i - 1] - k) {
add(f[i - 1][t],1ll * c[j - t - 1][a[i - 1] - k - 1] * f[i][j] % mod);
}
}
} else {
add(f[i - 1][j],f[i][j]);
}
}
}
}
int ans = 0;
rep(i,1,n + 1) add(ans,f[1][i]);
prt << ans;
}
} signed main() { Main::main(); return 0; }
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: -100
Wrong Answer
time: 12ms
memory: 4508kb
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:
0
result:
wrong answer 1st numbers differ - expected: '507010274', found: '0'