QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#296218 | #7875. Queue Sorting | ucup-team870# | WA | 48ms | 8832kb | C++14 | 1.8kb | 2024-01-02 14:47:01 | 2024-01-02 14:47:01 |
Judging History
answer
#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 IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
const int N=505,mod=998244353;
void add(ll &x,ll y){x=(x+y)%mod;}
int aa[N],a[N],suf[N];
ll C[N][N],pre[N][N],dp[N][N];
int main() {
IOS
const int M=500;
rep(i,0,M)C[i][0]=1,pre[i][0]=1;
rep(i,1,M){
rep(j,1,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod,pre[i][j]=(pre[i][j-1]+C[i][j])%mod;
}
// rep(i,1,5){
// rep(j,1,i)cout<<C[i][j]<<" ";
// cout<<endl;
// }
int n; cin>>n; int m=0;
rep(i,1,n)cin>>aa[i],m+=aa[i];
int tot=0;
rep(i,1,n){
if(aa[i])a[++tot]=aa[i];
}
n=tot;
per(i,n,1)suf[i]=suf[i+1]+a[i];
rep(i,1,m){
if(m-i+1<a[i])continue;
dp[n][i]=C[m-i][a[i]-1];
}
auto cal=[&](int x,int l,int r){
r=min(r,x);
ll res=pre[x][r];
if(l)res=(res-pre[x][l-1]+mod)%mod;
return res;
};
// cout<<cal(0,0,0)<<endl;
per(v,n-1,1){
rep(i,1,n){
if(m-i+1<suf[v])continue;
if(a[v]<=(m-i+1)-suf[v+1])add(dp[v][i],dp[v+1][i]); //j=i
rep(j,i+1,m){
if(m-j+1<suf[v+1])continue;
int l=max(0,a[v]+i-j),r=min(m-j+1-suf[v+1],a[v]-1);
// if(v==3 && i==1 ){
// cout<<j<<" "<<l<<" feafea "<<r<<endl;
// }
add(dp[v][i],dp[v+1][j]*cal(j-i-1,a[v]-1-r,a[v]-1-l)%mod);
}
}
}
// per(v,n,1){
// rep(i,1,n){
// if(dp[v][i])cout<<v<<" "<<i<<" "<<dp[v][i]<<endl;
// }
// }
cout<<dp[1][1]<<"\n";
}
/*
4
1 1 1 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8832kb
input:
4 1 1 1 1
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: -100
Wrong Answer
time: 48ms
memory: 8620kb
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:
478295689
result:
wrong answer 1st numbers differ - expected: '507010274', found: '478295689'