神仙套路题。
\(m=1，l=r\)
先将物品按价值排序。
则我们的初始状态一定是一个前缀。
显然我们的后继状态就是将若干个选择向后移动，并且不超过自己后面的。
注意到我们靠后的移动一定比考前的优，所以我们是现移动后面的再移动前面的。
我们记录四元组 \((le,pos,ri,val)\)。
表示前面还有 \(le\) 个可能要移动，第 \(le+1\) 个在 \(pos\)，下一个的位置为 \(ri\)，价值为 \(val\)。
显然可以转移向两个状态 \((le-1,le,pos,val)\) 和 \((le,pos+1,ri,val-s_{pos}+s_{pos+1})\)。
注意到前面的一个转移不太行，会算重，因为其实局面并没有发生改变。
所以我们考虑让 \(le\) 强制向前走一位，转移向 \((le-1,le+1,pos,val-s_{le}+s_{le+1})\)。
这样做是正确的，因为我们发现确实要至少走一位，因为不走后面的就走不动了，这样才是有意义的。
\(m\not ={1}，l\not ={r}\)
首先 \(l\not ={r}\) 是好处理的，只需要将长度在 \([l,r]\) 的前缀都加上就好了。
考虑记录三元组 \((pos,rank,val)\) 表示在第 \(i\) 种物品，正在其第 \(rank\) 大的选择方式，价值为 \(val\)。
显然可以转移 \((pos+1,1,val)\) 和 \((pos,rank+1,val-s_{pos,rank}+s_{pos,rank+1})\)。
但是第一个转移存在和之前相同的问题，会算重。
类似地，考虑将其修改为 \((pos+1,2,val-s_{pos+1,1}+s_{pos+1,2})\)。
这样做是没问题的，但是还是应该有不走的情况。
所以当 \(rank=2\) 时我们可以撤销自己转移向 \((pos+1,2,val-s_{pos,2}+s_{pos,1}-s_{pos+1,1}+s_{pos+1,2})\)。
但是这样有一个问题 \(-s_{pos,2}+s_{pos,1}-s_{pos+1,1}+s_{pos+1,2}\) 可能是一个负数，答案就不对。
我们可以自己创造单调性，将种类按 \(s_{2}-s_{1}\) 排序即可。
时间复杂度 \(O(klogn)\)。
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int f(0) ; rg char c(gc()) ;
while(!isdigit(c)) f |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (f?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; print(p...) ;
}
bool S_GND ;
const int N = 5e5+5 ;
const int INF = 1e18+7 ;
int n,k,m,al ;
struct S
{
int le,pos,ri,val ;
bool operator < (const S &A) const
{
return val > A.val ;
}
} ;
struct Sub
{
vector<int>num,res ;
priority_queue<S>q ;
void Init()
{
int le,ri,tot = 0,sum = 0 ; read(le,ri),ri = min(ri,(int)num.size()) ;
if(num.size() < le) {FOR(i,1,k,1) print(-1),enter ; exit(0) ; }
else if(!le) res.pb(0) ; sort(num.begin(),num.end()) ;
FOR(tot,0,ri-1,1)
{
int val = num[tot] ; sum += val ; if(tot < le) al += val ;
if(tot >= le-1) q.push({tot-1,tot,(int)num.size()-1,sum}) ;
}
}
void update()
{
if(q.empty()) {res.pb(INF) ; return ;}
auto [le,pos,ri,val] = q.top() ; q.pop(),res.pb(val) ;
if(pos < ri) q.push({le,pos+1,ri,val-num[pos]+num[pos+1]}) ;
if(le > -1 && le < pos-1) q.push({le-1,le+1,pos-1,val-num[le]+num[le+1]}) ;
}
int operator [] (const int &A)
{
while(res.size() < A) update() ;
return res[A-1] ;
}
}s[N] ;
int cmp(Sub x,Sub y)
{
return x[2]-x[1] < y[2]-y[1] ;
}
struct GB
{
int a,b,c ;
bool operator < (const GB &A) const
{
return c > A.c ;
}
} ;
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
// freopen("mami.in","r",stdin) ;
// freopen("mami.out","w",stdout) ;
read(n,m,k) ;
FOR(i,1,n,1)
{
int x,y ; read(x,y) ;
s[x].num.pb(y) ;
}
FOR(i,1,m,1) s[i].Init() ;
sort(s+1,s+1+m,cmp),print(al),enter,--k ;
priority_queue<GB>q ;
q.push({1,2,al-s[1][1]+s[1][2]}) ;
while(k)
{
auto [pos,rk,val] = q.top() ; q.pop() ;
if(val >= INF) break ; k-- ; print(val),enter ;
q.push({pos,rk+1,val-s[pos][rk]+s[pos][rk+1]}) ;
if(pos != m)
{
q.push({pos+1,2,val-s[pos+1][1]+s[pos+1][2]}) ;
if(rk == 2) q.push({pos+1,2,val-s[pos][2]+s[pos][1]-s[pos+1][1]+s[pos+1][2]}) ;
}
}
while(k--) print(-1),enter ;
return 0 ;
}