请各位大佬康康本人为什么会第一点过,其他全超时!
查看原帖
请各位大佬康康本人为什么会第一点过,其他全超时!
511042
Edwin_liannan楼主2022/1/15 10:57
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,f[200010],q1[200010],v,p;
priority_queue<ll> q;
struct gr{int p,v;}g[200010];
bool cmp(gr a,gr b){return a.p<b.p;};
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>g[i].p>>g[i].v;
	for(int i=1;i<=m;i++) cin>>f[i];
	sort(g+1,g+1+n,cmp);sort(f+1,f+1+m);
	while(p<n&&g[p].p<f[1]) v+=g[p++].v;q.push(v);
	for(int i=2;i<=m;i++){
		int h=0,t=0;ll ans=0,tmp=0,mx=0;
		while(p<n&&g[p].p<=f[i]) p++;
		for(int j=1;j<p;j++){
			q1[h++]=j,ans+=g[j].v,tmp+=g[j].v;
			while(h!=t&&(g[j].v-g[q1[t]].v)*2>=f[i]-f[i-1]) ans-=g[q1[t++]].p;
			mx=max(mx,ans);
		}
		q.push(mx),q.push(tmp-mx);
	}v=0;
	while(p<n) v+=g[p++].v;q.push(v);
	ll ans=0;
	for(int i=1;i<=k;i++) ans+=q.top(),q.pop();
	cout<<ans;
}
2022/1/15 10:57
加载中...