QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#458664 | #8839. Knocker | ucup-team3586# | WA | 47ms | 4960kb | C++23 | 1.3kb | 2024-06-29 18:13:44 | 2024-06-29 18:13:45 |
Judging History
answer
//Code by dXqwq, who is still searching painless suicide.
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int a[503];
bool b[503];
int nxt[503];
const int p=998244353;
int f[503][503];
signed main()
{
int n=read();
for(int i=1; i<=n; ++i) b[a[i]=read()]=1;
sort(a+1,a+n+1);
n=unique(a+1,a+n+1)-a-1;
for(int i=a[n]; i>=0; --i)
if(b[i]) nxt[i]=i;
else nxt[i]=nxt[i+1];
sort(a+1,a+n+1);
int ans=1;
for(int t=1; t<=a[n]; ++t) //first=t
{
memset(f,0,sizeof(f));
if(b[t]) f[t][t]=1;
else f[t+1][t]=1;
for(int i=t; i<a[n]; ++i)
{
for(int j=t; j<=i; ++j)
{
if(nxt[i]==nxt[i+1]&&i!=j)
{
if((i+1)-j<t)
f[i+1][j]=(f[i+1][j]+f[i][j])%p;
}
else
{
if((i+1)-j<t)
f[i+1][j]=(f[i+1][j]+f[i][j])%p;
f[i+1][i+1]=(f[i+1][i+1]+f[i][j])%p;
}
}
}
for(int i=t; i<=a[n]; ++i)
ans=(ans+f[a[n]][i])%p;
}
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4836kb
input:
1 5
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4960kb
input:
2 6 5
output:
7
result:
ok 1 number(s): "7"
Test #3:
score: 0
Accepted
time: 1ms
memory: 4836kb
input:
5 1 2 4 8 16
output:
69
result:
ok 1 number(s): "69"
Test #4:
score: 0
Accepted
time: 3ms
memory: 4772kb
input:
1 139
output:
71
result:
ok 1 number(s): "71"
Test #5:
score: 0
Accepted
time: 16ms
memory: 4792kb
input:
2 359 96
output:
3661
result:
ok 1 number(s): "3661"
Test #6:
score: 0
Accepted
time: 30ms
memory: 4852kb
input:
3 487 237 391
output:
1727635
result:
ok 1 number(s): "1727635"
Test #7:
score: 0
Accepted
time: 20ms
memory: 4792kb
input:
4 411 81 149 407
output:
789553
result:
ok 1 number(s): "789553"
Test #8:
score: 0
Accepted
time: 19ms
memory: 4824kb
input:
5 39 221 395 89 173
output:
29269116
result:
ok 1 number(s): "29269116"
Test #9:
score: 0
Accepted
time: 25ms
memory: 4956kb
input:
6 259 270 448 54 426 167
output:
813709483
result:
ok 1 number(s): "813709483"
Test #10:
score: 0
Accepted
time: 30ms
memory: 4872kb
input:
7 387 422 398 32 488 136 372
output:
407011330
result:
ok 1 number(s): "407011330"
Test #11:
score: 0
Accepted
time: 26ms
memory: 4772kb
input:
8 15 63 451 213 37 209 343 319
output:
141747374
result:
ok 1 number(s): "141747374"
Test #12:
score: 0
Accepted
time: 30ms
memory: 4852kb
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: 28ms
memory: 4768kb
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: 27ms
memory: 4872kb
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: 24ms
memory: 4824kb
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: 32ms
memory: 4772kb
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: 32ms
memory: 4824kb
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: 30ms
memory: 4848kb
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: 35ms
memory: 4852kb
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: 34ms
memory: 4820kb
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: 34ms
memory: 4788kb
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: 27ms
memory: 4844kb
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: 35ms
memory: 4836kb
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: 0
Accepted
time: 43ms
memory: 4824kb
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:
103940020
result:
ok 1 number(s): "103940020"
Test #25:
score: -100
Wrong Answer
time: 47ms
memory: 4848kb
input:
101 39 358 381 335 89 376 12 473 104 111 401 59 22 157 401 263 71 307 440 302 142 398 437 408 298 134 315 398 379 230 309 201 111 255 44 302 237 13 40 360 269 268 219 487 10 200 361 349 67 157 241 416 162 324 454 2 460 353 335 345 275 435 76 499 426 390 83 82 265 192 376 217 339 392 384 206 266 246 ...
output:
265095241
result:
wrong answer 1st numbers differ - expected: '265095240', found: '265095241'