1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
| #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i) char IO; int rd(){ int s=0; while(!isdigit(IO=getchar())); do s=(s<<1)+(s<<3)+(IO^'0'); while(isdigit(IO=getchar())); return s; } enum{N=200010,LINF=1ll<<60};
int n,m,k,I[N]; ll L; struct Group{ vector <int> A; int l,r,c; struct Node{ int l,p,r; ll s; bool operator < (const Node &__) const { return s>__.s; } }; priority_queue <Node> que; vector <ll> V; void Init(){ l=rd(),r=rd(),sort(A.begin(),A.end()),c=A.size(); if(c<l) { rep(i,1,k) puts("-1"); exit(0); } r=min(r,c); rep(i,0,l-1) L+=A[i]; ll s=0; if(!l) V.pb(0); rep(i,0,c-1) { if(i>=r) break; s+=A[i]; if(i>=l-1) que.push((Node){i-1,i,c-1,s}); } } void Next(){ if(que.empty()) return V.pb(LINF); Node t=que.top(); que.pop(); V.pb(t.s); if(t.p<t.r) que.push((Node){t.l,t.p+1,t.r,t.s-A[t.p]+A[t.p+1]}); if(~t.l && t.l<t.p-1) que.push((Node){t.l-1,t.l+1,t.p-1,t.s-A[t.l]+A[t.l+1]}); } ll operator [] (const int &k){ while((int)V.size()<k) Next(); return V[k-1]; } } S[N];
struct Node{ int x,y; ll s; bool operator < (const Node &__) const { return s>__.s; } }; priority_queue <Node> que;
int main(){ n=rd(),m=rd(),k=rd(); rep(i,1,n) { int x=rd(); S[x].A.pb(rd()); } rep(i,1,m) S[i].Init(); printf("%lld\n",L),k--; rep(i,1,m) I[i]=i; sort(I+1,I+m+1,[&](int x,int y){ return S[x][2]-S[x][1]<S[y][2]-S[y][1]; }); que.push((Node){1,2,L-S[I[1]][1]+S[I[1]][2]}); while(k) { Node t=que.top(); que.pop(); if(t.s>=LINF) break; k--,printf("%lld\n",t.s); int i=I[t.x],j=I[t.x+1]; que.push((Node){t.x,t.y+1,t.s-S[i][t.y]+S[i][t.y+1]}); if(j) que.push((Node){t.x+1,2,t.s-S[j][1]+S[j][2]}); if(t.y==2 && j) que.push((Node){t.x+1,2,t.s-S[i][2]+S[i][1]-S[j][1]+S[j][2]}); } while(k--) puts("-1"); }
|