QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#211497#4623. Matryoshka Dollyiyiyi#WA 205ms104956kbC++141.3kb2023-10-12 17:23:002023-10-12 17:23:00

Judging History

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

  • [2023-10-12 17:23:00]
  • 评测
  • 测评结果:WA
  • 用时:205ms
  • 内存:104956kb
  • [2023-10-12 17:23:00]
  • 提交

answer

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<bitset>
#include<set> 
#define ll long long
#define lowbit(x) x&(-x)
#define mp make_pair
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define forE(i,x) for(int i=head[x];i;i=nxt[i])
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=2e5+5;
const int mod=998244353;
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+(c-'0');
		c=getchar();
	}
	return x*f;
}
int T;
int a[maxn],b[maxn];
int f[5050][5050];
signed main()
{
	T=read();
	while(T--)
	{
		int n=read(),k=read(),d=read();
		rep(i,1,n) a[i]=read();
		rep(i,1,n)
		{
			int res=0;
			int l=1,r=i-1;
			while(l<=r)
			{
				int mid=(l+r)/2;
				if(a[i]-a[mid]>=d) l=mid+1,res=mid;
				else r=mid-1;
			}
			b[i]=res;
		}
		rep(i,0,n) rep(j,0,k) f[i][j]=0;
		f[0][0]=1;
		rep(i,1,n) rep(j,0,k) 
		{
			f[i][j]=1ll*(f[i-1][j]+1ll*f[i-1][j-1]*(1ll*(b[i]-(j-1)+mod)%mod)%mod)%mod;
		}
		printf("%d\n",f[n][n-k]);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 205ms
memory: 104956kb

input:

20
4 3 2
1 2 3 4
4 2 1
1 1 2 2
10 3 5
7 20 27 27 34 36 40 56 63 98
10 5 10
5 6 11 20 34 39 42 57 86 99
100 2 4
61 139 210 338 426 591 614 637 658 678 699 1002 1015 1162 1424 1433 1502 1756 1994 2073 2164 2189 2258 2305 2460 2464 2497 2507 2512 2526 2557 2742 2794 2809 3060 3075 3201 3226 3380 3576 3...

output:

3
2
0
10554
0
0
206258543
359242369
0
0
247697612
404757277
0
0
0
0
948502315
1
248027654
1

result:

wrong answer 3rd lines differ - expected: '2852', found: '0'