QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#276624	#7875. Queue Sorting	Bob_Wang	AC ✓	259ms	5592kb	C++14	1014b	2023-12-06 01:00:46	2023-12-06 01:00:46

Judging History

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

[2023-12-06 01:00:46]
评测

测评结果：AC
用时：259ms
内存：5592kb

查看

[2023-12-06 01:00:46]
提交

answer

#include<cstdio>
#define ll long long
#define maxn 505
using namespace std;

const ll mod=998244353;
int n,m;
int cnt[maxn],a[maxn];
ll dp[2][maxn][maxn];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&cnt[i]);
		for(int j=1;j<=cnt[i];++j)
		a[++m]=i;
	}
	dp[0][0][0]=1;
	for(int i=1;i<=m;++i)
	{
		int nw=(i&1);
		int lst=nw^1;
		for(int j=0;j<i;++j)
		for(int k=0;k<i;++k)
		dp[nw][j][i]=(dp[nw][j][i]+dp[lst][j][k])%mod;
		if(a[i]!=a[i-1])
		{
			for(int j=0;j<i;++j)
			{
				for(int k=0;k<j;++k)
				{
					dp[nw][j][j]=(dp[nw][j][j]+dp[lst][k][k])%mod;
					dp[nw][j][j]=(dp[nw][j][j]+dp[lst][k][i-1])%mod;
				}
			}
			
		}
		else
		{
			for(int j=0;j<i;++j)
			for(int k=0;k<j;++k)
			dp[nw][j][j]=(dp[nw][j][j]+dp[lst][k][k])%mod;
		}
		for(int j=0;j<=i;++j)
		for(int k=0;k<=i;++k)
		dp[lst][j][k]=0;
	}
	ll ans=0;
	for(int i=0;i<=m;++i)
	for(int j=0;j<=m;++j)
	ans=(ans+dp[m&1][i][j])%mod;
	printf("%lld",ans);
	return 0;
}

源文件, 语言: C++14

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 1580kb

input:

4
1 1 1 1

output:

result:

ok 1 number(s): "14"

Test #2:

score: 0

Accepted

time: 247ms

memory: 5572kb

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:

507010274

result:

ok 1 number(s): "507010274"

Test #3:

score: 0

Accepted

time: 259ms

memory: 5572kb

input:

500
1 1 0 2 1 0 2 3 2 0 0 2 0 2 1 1 0 0 1 1 1 2 1 1 1 0 1 1 2 2 1 4 0 2 1 0 2 3 1 0 1 1 0 2 1 2 2 1 0 0 3 1 4 1 1 2 1 1 0 1 3 1 2 0 0 0 2 1 2 0 0 3 2 1 1 1 1 1 2 1 0 1 0 0 0 1 0 0 2 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 2 1 1 0 1 1 0 1 1 0 0 1 0 3 1 3 0 0 2 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 2 0 0 ...

output:

result:

ok 1 number(s): "7590964"

Test #4:

score: 0

Accepted

time: 234ms

memory: 5436kb

input:

200
3 1 0 3 2 1 0 3 1 1 2 3 3 1 6 2 1 3 2 1 1 2 1 2 1 5 2 2 3 4 0 4 2 1 2 2 0 2 3 1 2 3 6 3 2 3 2 2 4 2 7 2 1 5 1 9 0 4 4 8 3 3 3 1 3 0 2 2 8 1 3 5 4 3 0 6 1 6 1 3 4 2 2 1 1 4 4 4 1 0 4 3 4 3 3 0 3 2 0 0 3 4 0 3 1 3 2 4 3 2 0 3 2 2 3 2 2 2 1 2 2 1 0 2 0 3 1 3 5 1 3 3 6 5 3 2 2 2 3 6 2 0 5 2 2 2 2 1 ...

output:

507844569

result:

ok 1 number(s): "507844569"

Test #5:

score: 0

Accepted

time: 51ms

memory: 4004kb

input:

100
4 8 2 5 4 4 3 0 2 7 2 3 4 4 1 2 3 4 4 4 3 3 3 3 3 2 4 1 3 5 5 1 4 6 1 1 1 3 2 3 2 1 0 1 4 4 2 4 2 5 3 5 1 6 2 3 3 1 4 4 4 1 4 4 3 4 2 0 2 3 6 1 3 3 5 4 1 1 2 3 0 3 2 2 1 3 3 2 5 6 3 2 3 3 5 4 2 3 4 4

output:

989550242

result:

ok 1 number(s): "989550242"

Test #6:

score: 0

Accepted

time: 0ms

memory: 1624kb

input:

1
1

output:

result:

ok 1 number(s): "1"

Test #7:

score: 0

Accepted

time: 0ms

memory: 1628kb

input:

500
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

result:

ok 1 number(s): "1"

Test #8:

score: 0

Accepted

time: 0ms

memory: 1768kb

input:

10
2 1 3 3 2 3 1 1 3 1

output:

165452340

result:

ok 1 number(s): "165452340"

Test #9:

score: 0

Accepted

time: 0ms

memory: 1636kb

input:

20
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0

output:

result:

ok 1 number(s): "2"

Test #10:

score: 0

Accepted

time: 0ms

memory: 1648kb

input:

20
0 0 1 0 0 0 0 1 0 0 0 0 0 0 2 0 1 0 0 0

output:

result:

ok 1 number(s): "28"

Test #11:

score: 0

Accepted

time: 0ms

memory: 1556kb

input:

10
1 1 1 1 1 1 1 1 1 1

output:

result:

ok 1 number(s): "16796"

Test #12:

score: 0

Accepted

time: 60ms

memory: 4024kb

input:

300
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

431279497

result:

ok 1 number(s): "431279497"

Test #13:

score: 0

Accepted

time: 207ms

memory: 5576kb

input:

2
232 268

output:

929717758

result:

ok 1 number(s): "929717758"

Test #14:

score: 0

Accepted

time: 214ms

memory: 5588kb

input:

1
500

output:

result:

ok 1 number(s): "1"

Test #15:

score: 0

Accepted

time: 206ms

memory: 5592kb

input:

3
155 180 165

output:

911108550

result:

ok 1 number(s): "911108550"

Extra Test:

score: 0

Extra Test Passed