QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#623334 | #7875. Queue Sorting | argtarg | RE | 1ms | 5644kb | C++20 | 1.2kb | 2024-10-09 11:23:57 | 2024-10-09 11:23:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int, int>
void solve();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--)solve();
return 0;
}
const int mod = 998244353;
const int N = 510;
int C[N][N];
void init(){
for(int i=0;i<N;i++)C[i][0]=1;
for(int i=1;i<N;i++){
for(int j=1;j<=i;j++){
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
}
void solve() {
init();
int n;
cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
vector<vector<int>>dp(n+1,vector<int>(n+1));
int sum=0;
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=sum;j++){
dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
for(int num=1;num<=a[i];num++){//num in front
for(int k=j+num;k<=sum+num-1;k++){
dp[i][k]=(dp[i][k]+dp[i-1][j]*C[k-j-1][num-1])%mod;
}
}
}
//j=sum
sum+=a[i];
}
int ans=0;
for(int i=0;i<=n;i++)ans=(ans+dp[n][i])%mod;
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5644kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: -100
Runtime Error
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 ...