ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#198431 | #2301. 青蛙 | ysys | 100 | 664ms | 7520kb | C++11 | 1.9kb | 2023-11-26 09:10:31 | 2023-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;
}
Details
小提示:点击横条可展开更详细的信息
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