QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#296218#7875. Queue Sortingucup-team870#WA 48ms8832kbC++141.8kb2024-01-02 14:47:012024-01-02 14:47:01

Judging History

你现在查看的是最新测评结果

  • [2024-01-02 14:47:01]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:8832kb
  • [2024-01-02 14:47:01]
  • 提交

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'