UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#198459#2301. 青蛙hegm100293ms3172kbC++1.2kb2023-11-26 11:42:282023-11-26 12:06:26

answer

#include<bits/stdc++.h>
#define N 100005
#define int long long
#define inf 2000000000000000000ll
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int t,n,m,k,d,a[N],c[N],sum,ans;
queue<int> q;
bool solve(int x)
{
	while(q.size())q.pop();
	if(x==0)return 0;int tot=0;
	for(int i=1;i<=x;i++)
	{
		q.push(1);
		tot+=c[m-i+1];
	}
	for(int i=1;i<=k;i++)
	{
		if(a[i]-q.front()>d)return 0;
		q.push(a[i]);q.pop();
	}
	while(q.size())
	{
		if(n-q.front()>d)return 0;
		q.pop();
	}
	ans=min(ans,sum-tot);
	return 1;
}
signed main()
{
	t=read();
	while(t--)
	{
		n=read();m=read();sum=0;
		k=read();d=read();ans=inf;
		for(int i=1;i<=m;i++)c[i]=read(),sum+=c[i];
		for(int i=1;i<=k;i++)a[i]=read();
		sort(c+1,c+1+m);sort(a+1,a+1+k);
		if(d>n-1)
		{
			cout<<"0\n";
			continue;
		}
		a[0]=1;a[k+1]=n;int num=0; 
		for(int i=1;i<=k+1;i++)
		{
			if(a[i]-a[i-1]>d)
			num++;
		}
		if(num)ans=sum-c[1]+c[1]*num;
		else ans=sum-c[m];
		int l=1,r=m,mid;
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(solve(mid))l=mid+1;
			else r=mid-1;
		}
		cout<<ans<<"\n"; 
	}
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 27
Accepted

Test #1:

score: 27
Accepted
time: 1ms
memory: 1228kb

input:

10
1000000000 50 100 624152212
287318519 995674205 549237435 170798520 633865780 838468389 200699776...

output:

0
17529035715
11518101397
21311374194
19118405214
22928091687
19618584985
0
10
10

result:

ok 10 lines

Subtask #2:

score: 29
Accepted

Test #2:

score: 29
Accepted
time: 0ms
memory: 1252kb

input:

10
1000000000 1000 1000 94114823
635260751 976925770 890478319 219465138 919384021 662750421 2221426...

output:

406166890378
474204100112
427847425637
389134853484
373166426525
472067494703
422182402595
289090274...

result:

ok 10 lines

Subtask #3:

score: 44
Accepted

Test #3:

score: 44
Accepted
time: 292ms
memory: 3172kb

input:

10
1000000000 100000 100000 104781403
63438245 942327368 55027925 774793131 446601855 901674548 2445...

output:

37728059175391
46669158099739
46696135907077
46669733668272
40567588097618
41994946214524
4684093566...

result:

ok 10 lines