比赛 |
EYOI暨SBOI暑假快乐赛2nd |
评测结果 |
WWWWWWWWWWWWWWWWWWWWW |
题目名称 |
最近的母牛获胜 |
最终得分 |
0 |
用户昵称 |
lavey |
运行时间 |
3.966 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2022-06-26 11:24:00 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=400050;
struct node
{
int typ;//1为草地,2为牛
int pos;
int w;
}t[N];
struct line
{
long long w;
int id;
}p1[N],p2[N],p[N];
int k,m,n;
long long ans;
bool vis[N];
char ch;
inline void read(int &x){x=0,ch=getchar();while(ch<48||ch>57)ch=getchar();while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}
inline bool cmp1(node a,node b)
{
return a.pos<b.pos;
}
inline bool cmp2(line a,line b)
{
return a.w>b.w;
}
int main()
{
freopen("Closest_Cow_Wins.in","r",stdin);
freopen("Closest_Cow_Wins.out","w",stdout);
read(k),read(m),read(n);
for(int i=1;i<=k;++i) read(t[i].pos),read(t[i].w),t[i].typ=1;
for(int i=k+1;i<=k+m;++i) read(t[i].pos),t[i].typ=2;
sort(t+1,t+k+m+1,cmp1);
int s=1,mx=0,cnt=1;
long long sum=0;
while(t[s].typ==1)
{
sum+=t[s].w;
mx=max(mx,t[s].w);
++s;
}
if(sum) p1[cnt].w=sum,p1[cnt].id=cnt,++cnt;
int idx=1;
sum=mx=0;
for(int i=s+1;i<=k+m;++i)
{
if(t[i].typ==2&&sum!=0)
{
p1[cnt].w=mx,p1[cnt].id=cnt;
if(sum!=mx) p2[cnt].w=sum-mx,p2[cnt].id=cnt,p[idx].w=sum,p[idx++].id=cnt;
++cnt;
sum=mx=0;
}
else
{
sum+=t[i].w;
mx=max(mx,t[i].w);
}
}
if(sum) p1[cnt].w=sum,p1[cnt].id=cnt;
sort(p+1,p+idx+1,cmp2);
sort(p1+1,p1+cnt+1,cmp2);
sort(p2+1,p2+cnt+1,cmp2);
cout<<idx<<endl;
int nw=1;
for(int i=1;i<=n/2;++i) ans+=p[i].w,vis[p[i].id]=1;
if(n%2==1)
{
ans+=p1[nw].w;
++nw;
}
for(int i=cnt;i>=1;--i)
{
if(!vis[p2[i].id]) continue;
cout<<i<<endl;
while(vis[p1[nw].id]) ++nw;
if(nw>cnt) break;
if(p1[nw].w>p2[i].w)
{
ans-=p2[i].w;
ans+=p1[nw].w;
++nw;
}
}
printf("%lld\n",ans);
return 0;
}