洛谷题解

#include<algorithm> #include<cstdio> #include<vector> #include<queue> #define ll long long #define pb push_back #define MaxN 200500 using namespace std; const ll INF=1ll<<60; struct Data{ int x,y,z;ll sum; bool operator < (const Data &A) const {return sum>A.sum;} }; struct SeqDS { vector<ll> ans; vector<int> a; priority_queue<Data> q; int l,r; void calc(int p) { if (p<ans.size())return ; if (q.empty()){ans.pb(INF);return ;} Data now=q.top();q.pop(); int x=now.x,y=now.y,z=now.z;ll sum=now.sum; ans.pb(sum); if (za.size()-1&&x+1y&&y+1<r)q.push((Data){x+1,y+1,z,sum+a[y+1]}); if (y>=0&&y+1<=z)q.push((Data){x,y+1,z,sum-a[y]+a[y+1]}); if (x>=0&&x+1<y)q.push((Data){x-1,x+1,y-1,sum-a[x]+a[x+1]}); } void Init() { sort(a.begin(),a.end()); if (l>a.size()){ans.pb(INF);ans.pb(INF);return ;} r=min(r,(int)a.size()); ll sum0=0; for (int i=0;i<l;i++)sum0+=a[i]; q.push((Data){l-2,l-1,a.size()-1,sum0}); calc(0);calc(1); } }T[MaxN]; struct Data2{ int p,j;ll sum; bool operator < (const Data2 &A) const {return sum>A.sum;} }; int tp[MaxN]; bool cmp(int A,int B) {return T[A].ans[1]-T[A].ans[0]<T[B].ans[1]-T[B].ans[0];} priority_queue<Data2> q; int n,m,k; int main() { scanf("%d%d%d",&n,&m,&k); for (int i=1,c,x;i<=n;i++){ scanf("%d%d",&c,&x); T[c].a.pb(x); } ll sum0=0; for (int i=1;i<=m;i++){ scanf("%d%d",&T[i].l,&T[i].r); T[i].Init();tp[i]=i; sum0=min(INF,sum0+T[i].ans[0]); } sort(tp+1,tp+m+1,cmp); int cnt=0; q.push((Data2){0,0,sum0}); while(cnt<k&&!q.empty()){ Data2 now=q.top();q.pop(); int p=now.p,j=now.j;ll sum=now.sum; if (sum>=INF)break; printf("%lld\n",sum);cnt++; if (p<m&&j==1) q.push((Data2){p+1,1,sum-T[tp[p]].ans[1]+T[tp[p]].ans[0]-T[tp[p+1]].ans[0]+T[tp[p+1]].ans[1]}); if (p<m) q.push((Data2){p+1,1,sum-T[tp[p+1]].ans[0]+T[tp[p+1]].ans[1]}); if (p>=1){ T[tp[p]].calc(j+1); q.push((Data2){p,j+1,sum-T[tp[p]].ans[j]+T[tp[p]].ans[j+1]}); } }for (int i=cnt+1;i<=k;i++)puts("-1"); return 0; }