QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#350674 | #7875. Queue Sorting | wtz2333 | WA | 99ms | 9732kb | C++17 | 1.9kb | 2024-03-11 00:10:06 | 2024-03-11 00:10:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1010;
using ll = long long;
const int mo = 998244353;
int C[maxn][maxn];
int dp[maxn][maxn];
void upd(int &x,int y) {
(x += y) >= mo ? (x -= mo) : x;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a;
for(int i = 1;i <= n;i ++) {
int x;
cin >> x;
if(x) a.push_back(x);
}
n = a.size();
if(n == 0) {
cout << 1 << endl;
return 0;
}
C[0][0] = 1;
for(int i = 1;i <= 1000;i ++) {
C[i][0] = 1;
for(int j = 1;j <= i;j ++) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mo;
}
}
auto calc = [&](int m,int n) {
if(n == 0) return 1;
return C[n + m - 1][n - 1];
};
// cerr << n << endl;
dp[n][a.back()] = 1;
int sum = a.back();
for(int i = n - 1;i >= 1;i --) {
for(int j = 1;j <= sum;j ++) {
for(int k = 1;k <= a[i - 1];k ++) {
for(int p = 1;p <= j;p ++) {
int endlen = j - p + 1;
upd(dp[i][endlen + a[i - 1] - k],1ll * dp[i + 1][j] * calc(k - 1,j) % mo);
// upd(dp[i][k + p],1ll * dp[i + 1][j] * calc(k,j,p) % mo);
// cerr << i + 1 << " " << j << " " << dp[i + 1][j] << endl;
// cerr << i << " " << k + p << " " << dp[i][k + p] << endl;
// cerr << endl;
}
}
upd(dp[i][j + a[i - 1]],dp[i + 1][j]);
// cerr << endl;
// cerr << i << " " << j << " " << dp[i][j] << endl;
// cerr << endl;
}
sum += a[i - 1];
}
ll ans = 0;
for(int i = 1;i <= sum;i ++) ans = (ans + dp[1][i]) % mo;
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9732kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: -100
Wrong Answer
time: 99ms
memory: 9296kb
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:
295951759
result:
wrong answer 1st numbers differ - expected: '507010274', found: '295951759'