ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#198459 | #2301. 青蛙 | hegm | 100 | 293ms | 3172kb | C++ | 1.2kb | 2023-11-26 11:42:28 | 2023-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