UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198431#2301. 青蛙ysys100664ms7520kbC++111.9kb2023-11-26 09:10:312023-11-26 12:01:32

answer

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(b);i>=(a);i--)
#define endl "\n"
#define For(i,u) for(int i=head[u];i;i=e[i].next)
#define V vector<int>
#define VV vector<V>
#define Debug(a) cout<<"QwQ "<<a<<endl;
#define FST NOT_FST
#define trash_round unrated
#define pint pair<int,int>
#define fi first
#define se second
#define Vp vector<pint>
const int MOD=1e9+7;
using namespace std;
int n,m;
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;
}
string reads()
{
	char ch=getchar();string s;
	while(ch<'a'||ch>'z'){ch=getchar();}
	while(ch>='a'&&ch<='z'){s+=ch;ch=getchar();}
	return s;
}
char readc()
{
	char ch=getchar();
	while(ch<'a'||ch>'z') ch=getchar();
	return ch;
}

// down is mytrue code ------------------------------

const int N=1e6+5;

int a[N],c[N];

const int INF=2e9;

set<int>st;

void solve()
{
	int n=read(),m=read(),k=read(),d=read();
	rep(i,1,m)
	{
		c[i]=read();
	}
	rep(i,1,k)
	{
		a[i]=read();
	}
	sort(a+1,a+1+k);
	sort(c+1,c+1+m);
	a[0]=1;
	a[k+1]=n;
	int ans=0,flag=0;
	rep(i,1,k+1)
	{
		if(a[i]-a[i-1]>d)
		{
			ans+=c[1];
			flag=1;
		}
	}
	if(flag) {rep(i,2,m) ans+=c[i];cout<<ans<<endl;return;}
	st.clear();
	st.insert(INF);
	rep(i,0,k+1) {st.insert(a[i]);}
	per(i,1,m)
	{
		int it=1;
		queue<int>q;
		while(it!=n)
		{
			int to=*prev(st.upper_bound(it+d));
			if(!(to>it&&to<=it+d)) {flag=1;break;}
			if(to!=n) q.push(to);
			it=to;
		}
		if(flag)
		{
			rep(j,1,i)
			{
				ans+=c[j];
			}
			cout<<ans<<endl;
			return;
		}
		while(!q.empty())
		{
			int u=q.front();
			st.erase(u);
			q.pop();
		}
	}
	cout<<0<<endl;
	return;
}

signed main()
{
	int t=read();
	while(t--)
	{
		solve();
	}
	return 0;
}


详细

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

Subtask #1:

score: 27
Accepted

Test #1:

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

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: 5ms
memory: 1292kb

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: 658ms
memory: 7520kb

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