QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#273266#7875. Queue Sortingucup-team093#WA 62ms4628kbC++201.0kb2023-12-02 22:35:122023-12-02 22:35:12

Judging History

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

  • [2023-12-02 22:35:12]
  • 评测
  • 测评结果:WA
  • 用时:62ms
  • 内存:4628kb
  • [2023-12-02 22:35:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 510, P = 998244353;

int c[N][N];

int main() {
    for(int i = 0; i < N; i ++) {
        c[i][0] = 1;
        for(int j = 1; j <= i; j ++)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
    }
    int n, len = 0, sum = 0;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    len = accumulate(a.begin(), a.end(), 0);
    vector<int> dp(len + 1, 0);
    for(int i = 1; i <= len; i ++)
        dp[i] = (P + c[i][a[0]] - c[i - 1][a[0]]) % P;
    
    sum = a[0];
    for(int i = 1; i < n; i ++) {
        vector<int> tmp(len + 1, 0);
        for(int j = 1; j <= len; j ++) {
            for(int k = 0, uk = min(j - sum, a[i]); k <= uk; k ++)
                for(int l = j; l <= len; l ++)
                    tmp[l] = (tmp[l] + dp[j] * (long long)(P + c[l - j][a[i] - k] - (l > j ? c[l - j - 1][a[i] - k] : 0))) % P; 
        }
        swap(tmp, dp);
        sum += a[i];
    }
    cout << dp[len];
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4596kb

input:

4
1 1 1 1

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: -100
Wrong Answer
time: 62ms
memory: 4628kb

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'