QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#458664#8839. Knockerucup-team3586#WA 47ms4960kbC++231.3kb2024-06-29 18:13:442024-06-29 18:13:45

Judging History

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

  • [2024-06-29 18:13:45]
  • 评测
  • 测评结果:WA
  • 用时:47ms
  • 内存:4960kb
  • [2024-06-29 18:13:44]
  • 提交

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'