QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#459577	#8839. Knocker	ucup-team1231^#	WA	84ms	5972kb	C++20	1.4kb	2024-06-30 08:43:08	2024-06-30 08:43:08

Judging History

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

[2024-06-30 08:43:08]
评测

测评结果：WA
用时：84ms
内存：5972kb

查看

[2024-06-30 08:43:08]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef vector<int> vi;
#define MOD 998244353

int a[500];
int dp[2][505][505];
int main() {
    int i;
    int n;
    scanf("%d",&n);
    for (i = 0; i < n; i++) scanf("%d",&a[i]);
    sort(a,a+n);
    n = unique(a,a+n)-a;

    int j,k,l,ans = 1;
    for (i = 1; i <= 501; i++) dp[n & 1][i][502] = 1;
    for (i = n-1; i >= 0; i--) {
        int p = i & 1;
        memset(dp[p],0,sizeof(dp[p]));
        for (j = 1; j <= 501; j++) {
            vi pre(510);
            for (k = 0; k < 504; k++) pre[k+1] = (pre[k]+dp[!p][j][k]) % MOD;
            for (k = max(a[i]-j+1,0); k <= a[i]; k++) {
                dp[p][j][k] += dp[!p][j][k];
                dp[p][j][k] += pre[504]-pre[a[i]+1];
                dp[p][j][k] %= MOD;
                // for (l = k+1; l <= 502; l++) {
                //     if ((l > k) && (l < a[i]+1)) continue;
                //     dp[p][j][k] += dp[!p][j][l];
                //     dp[p][j][k] %= MOD;
                // }
            }
        }
        for (j = max(a[i]/2+1,(i == 0) ? 1:a[i-1]+1); j <= a[i]; j++) {
            ans += dp[p][j][j];
            //cout << i << "," << j << "," << j << ": " << dp[p][j][j] << endl;
            ans %= MOD;
        }
    }
    if (ans < 0) ans += MOD;
    printf("%d\n",ans);

    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 5852kb

input:

1
5

output:

result:

ok 1 number(s): "4"

Test #2:

score: 0

Accepted

time: 3ms

memory: 5908kb

input:

2
6 5

output:

result:

ok 1 number(s): "7"

Test #3:

score: 0

Accepted

time: 5ms

memory: 5868kb

input:

5
1 2 4 8 16

output:

result:

ok 1 number(s): "69"

Test #4:

score: 0

Accepted

time: 2ms

memory: 5896kb

input:

1
139

output:

result:

ok 1 number(s): "71"

Test #5:

score: 0

Accepted

time: 3ms

memory: 5972kb

input:

2
359 96

output:

result:

ok 1 number(s): "3661"

Test #6:

score: 0

Accepted

time: 2ms

memory: 5920kb

input:

3
487 237 391

output:

result:

ok 1 number(s): "1727635"

Test #7:

score: 0

Accepted

time: 0ms

memory: 5824kb

input:

4
411 81 149 407

output:

result:

ok 1 number(s): "789553"

Test #8:

score: 0

Accepted

time: 6ms

memory: 5964kb

input:

5
39 221 395 89 173

output:

29269116

result:

ok 1 number(s): "29269116"

Test #9:

score: 0

Accepted

time: 3ms

memory: 5780kb

input:

6
259 270 448 54 426 167

output:

813709483

result:

ok 1 number(s): "813709483"

Test #10:

score: 0

Accepted

time: 8ms

memory: 5920kb

input:

7
387 422 398 32 488 136 372

output:

407011330

result:

ok 1 number(s): "407011330"

Test #11:

score: 0

Accepted

time: 6ms

memory: 5968kb

input:

8
15 63 451 213 37 209 343 319

output:

141747374

result:

ok 1 number(s): "141747374"

Test #12:

score: 0

Accepted

time: 10ms

memory: 5780kb

input:

9
439 407 197 191 291 486 30 307 11

output:

727389889

result:

ok 1 number(s): "727389889"

Test #13:

score: 0

Accepted

time: 9ms

memory: 5924kb

input:

10
18 18 71 471 121 362 467 107 138 254

output:

118253787

result:

ok 1 number(s): "118253787"

Test #14:

score: 0

Accepted

time: 12ms

memory: 5780kb

input:

11
146 171 316 449 375 434 450 299 202 232 157

output:

400144492

result:

ok 1 number(s): "400144492"

Test #15:

score: 0

Accepted

time: 8ms

memory: 5840kb

input:

12
70 311 74 427 232 211 126 83 357 118 97 428

output:

462347314

result:

ok 1 number(s): "462347314"

Test #16:

score: 0

Accepted

time: 10ms

memory: 5924kb

input:

13
494 155 320 96 486 476 313 71 13 301 332 376 269

output:

88111202

result:

ok 1 number(s): "88111202"

Test #17:

score: 0

Accepted

time: 11ms

memory: 5920kb

input:

14
418 204 77 278 239 457 284 263 372 279 476 416 360 18

output:

651058833

result:

ok 1 number(s): "651058833"

Test #18:

score: 0

Accepted

time: 15ms

memory: 5908kb

input:

15
46 344 323 255 301 234 472 47 28 165 415 159 450 451 336

output:

772893469

result:

ok 1 number(s): "772893469"

Test #19:

score: 0

Accepted

time: 12ms

memory: 5960kb

input:

16
174 188 377 437 54 498 455 239 183 347 59 199 52 488 147 82

output:

972620652

result:

ok 1 number(s): "972620652"

Test #20:

score: 0

Accepted

time: 16ms

memory: 5924kb

input:

17
394 137 134 107 104 275 130 227 339 326 499 251 142 421 470 499 188

output:

899401071

result:

ok 1 number(s): "899401071"

Test #21:

score: 0

Accepted

time: 19ms

memory: 5900kb

input:

18
22 481 380 288 166 348 113 215 198 212 246 494 233 459 293 416 318 467

output:

412927759

result:

ok 1 number(s): "412927759"

Test #22:

score: 0

Accepted

time: 15ms

memory: 5908kb

input:

19
446 30 434 62 123 317 289 203 354 394 390 238 323 392 308 333 233 25 259

output:

769017546

result:

ok 1 number(s): "769017546"

Test #23:

score: 0

Accepted

time: 20ms

memory: 5780kb

input:

20
440 204 481 140 310 354 34 150 184 360 16 301 290 178 138 393 399 260 381 499

output:

602957116

result:

ok 1 number(s): "602957116"

Test #24:

score: -100

Wrong Answer

time: 84ms

memory: 5968kb

input:

100
115 14 432 165 28 396 133 293 448 428 257 20 432 120 90 142 157 353 218 358 394 121 427 229 237 222 94 345 67 360 83 123 320 323 435 393 303 142 6 146 168 346 234 125 117 116 50 105 449 191 423 376 69 300 58 268 381 232 288 41 264 329 37 413 395 25 106 459 474 58 31 135 16 380 113 480 310 459 18...

output:

520051071

result:

wrong answer 1st numbers differ - expected: '103940020', found: '520051071'