原文链接 www.cnblogs.com/zhouzhendong/p/UOJ318.html
我怎么越来越菜了。
首先,对于一个物品,我们将它拆成若干份:最后一天拆成两份,一份的个数为1 ,价值为 a+s;另一份的个数为 (c-1) mod x,价值为 a。对于在 $(c-1) / x $ 天以及以前,每天有一份个数为 x,价值为 a 的物品。
于是,用堆维护物品,每次取最大价值的,就可以在 \(O(n ^ 2 m \log n)\) 的时间复杂度内得到一个询问的答案。
考虑将所有物品分成两种:
然后同样用堆维护,可以做到 \(O(n m\log n)\) 回答单次询问。
如果我们得到了 \(k\) 天的答案,那么我们只需要扔掉价值最小的一些物品,使得剩余物品数 \(\leq (k-1) m\) ,就可以得到 \(k-1\) 天的答案。
于是我们只需要算出 100000 天的答案,然后倒推,即可预处理出所有询问的答案。
总时间复杂度 \(O(nm\log n+ k)\)。
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"---------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
LL read(){
LL x=0,f=0;
char ch=getchar();
while (!isdigit(ch))
f|=ch=='-',ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
const int N=100005;
int n,m,k;
int lim=1e5;
struct Node{
int type,T;
LL x;
int v,X;
Node(){}
Node(int _t,int _x,int _v){
type=_t,x=X=_x,v=_v;
}
friend bool operator < (Node a,Node b){
return a.v<b.v;
}
};
vector <Node> A[N];
priority_queue <int,vector <int>,greater <int> > Q;
priority_queue <Node> q;
vector <Node> tmp;
LL res[N];
int main(){
n=read(),m=read(),k=read();
For(i,1,lim)
A[i].clear();
For(i,1,n){
int a=read(),s=read(),c=read(),x=read();
if (!c)
continue;
if (x>0){
int las=c/x+1,rem=c%x;
if (rem==0)
las--,rem=x;
las=min(las,lim-1);
A[las].pb(Node(0,1,a+s));
A[las].pb(Node(0,rem-1,a));
A[las-1].pb(Node(1,x,a));
}
else {
A[lim].pb(Node(0,1,a+s));
A[lim].pb(Node(0,c-1,a));
}
}
LL ans=0;
Fod(i,lim,1){
for (auto v : A[i]){
Node vv=v;
vv.T=i;
q.push(vv);
}
tmp.clear();
For(cc,1,m){
if (q.empty())
break;
Node now=q.top();
q.pop();
if (now.T>i&&now.type==1)
now.x+=(LL)(now.T-i)*now.X,now.T=i;
if (now.x==0){
if (now.type==1)
tmp.pb(now);
cc--;
continue;
}
ans+=now.v;
Q.push(now.v);
now.x--;
q.push(now);
}
while (!tmp.empty())
q.push(tmp.back()),tmp.pop_back();
}
Fod(i,lim,1){
res[i]=ans;
while (Q.size()>m*(i-1)){
ans-=Q.top();
Q.pop();
}
}
while (k--)
printf("%lld\n",res[read()]);
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章