[NOI2017]蔬菜
大意就是有\(n\)种物品，第\(i\)个物品有\(c_i\)个，单价是\(a_i\)。然后每天你可以卖出最多\(m\)个物品。每天结束后第\(i\)种物品会减少\(x_i\)个。第一次出售\(i\)物品时还会额外获得\(s_i\)的收益。
每次询问给出\(p\)，问\(p\)天能得到的最大收益。
\(1\leq n,p\leq 10^5,1\leq m\leq 10,1\leq a_i,c_i\leq 10^9\)。
神仙题啊！不会网络流，不会贪心，直接自闭。
60分的网络流做法
因为很容易发现这个题状态太大，无法\(DP\)，所以我们考虑费用流之类的东西。然后我们发现这个题每个物品的上限时刻在变化，很难建图。
对于这种流量变化的费用流我们考虑拆点。我们将每种蔬菜拆成\(P\)个点，第\(i\)个点到汇点的流量就是第\(i\)天比第\(i+1\)天多的数量。我们还应该额外拆一个点表示第一次出售。然后第\(i\)个点向第\(i+1\)个点连边。
我们增广\(P\)次，就得到了\(1\)到\(P\)的答案。
100分的贪心算法
我们发现每天有蔬菜减少非常不好做，于是我们考虑倒着做。这样相当于每天我们会得到一些蔬菜。所以我们就可以每次选收益最大的蔬菜来卖。
具体实现有点复杂。先开一个堆。记录每种蔬菜最晚在什么时候出现。当倒推到第\(i\)天时，将在最晚在当天出现的蔬菜丢进堆里。每次取堆顶的蔬菜来卖。
这样我们就得到了\(P\)天的答案。
然后考虑递推出\(1\)到\(P-1\)的答案。相当于说我们要把卖出的蔬菜删除掉。一个比较显然的结论就是我们尽量在天数偏小的时候删除（因为我们卖蔬菜肯定也是越早卖越好）。删除的时候就一直删除当前价值最小的。
不用考虑会不会删除操作时出现了不合法的情况。因为我们发现删除的时间是没有影响的。可以这么感性理解分析：假设我们递推到第\(i\)天，要删除一些第\(k\)种蔬菜，那么我们就将相应的卖出操作撤销，在它之后的卖出操作全部提前，这肯定也是合法的。
据说这就是模拟费用流。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
int n,m,k;
ll ans;
int a[N],s[N],c[N],x[N];
struct node {
ll id,val;
node() {val=id=0;}
node(int i,int v) {val=v,id=i;}
bool operator <(const node &a)const {return val<a.val;}
};
priority_queue<node>q;
const int P=100000;
int sold;
vector<int>ap[N];
vector<int>tem;
int used[N];
ll Ans[N];
int main() {
n=Get(),m=Get(),k=Get();
for(int i=1;i<=n;i++) {
a[i]=Get(),s[i]=Get(),c[i]=Get(),x[i]=Get();
if(!x[i]) ap[P].push_back(i);
else ap[min(P,(c[i]+x[i]-1)/x[i])].push_back(i);
}
for(int i=P;i>=1;i--) {
for(int j=0;j<ap[i].size();j++) {
q.push(node(ap[i][j],s[ap[i][j]]+a[ap[i][j]]));
}
tem.clear();
int res=m;
while(res) {
if(!q.size()) break;
int id=q.top().id,val=q.top().val;
q.pop();
if(!used[id]) {
res--;
used[id]=1;
ans+=val;
q.push(node(id,a[id]));
} else {
int now=min(res,c[id]-used[id]-(i-1)*x[id]);
res-=now;
used[id]+=now;
ans+=1ll*now*val;
if(used[id]<c[id]) tem.push_back(id);
}
}
sold+=m-res;
for(int j=0;j<tem.size();j++) q.push(node(tem[j],a[tem[j]]));
}
while(q.size()) q.pop();
for(int i=1;i<=n;i++) {
if(used[i]==1) q.push(node(i,-s[i]-a[i]));
else if(used[i]>1) q.push(node(i,-a[i]));
}
Ans[P]=ans;
for(int i=P;i>1;i--) {
tem.clear();
int res=max(0,sold-(i-1)*m);
while(res) {
if(!q.size()) break;
int id=q.top().id,val=q.top().val;
q.pop();
if(used[id]==1) {
sold--;
used[id]--;
res--;
ans+=val;
} else {
int now=min(res,used[id]-1);
used[id]-=now;
res-=now;
ans+=1ll*now*val;
sold-=now;
if(used[id]==1) q.push(node(id,-s[id]-a[id]));
else q.push(node(id,-a[id]));
}
}
Ans[i-1]=ans;
}
while(k--) {
int x=Get();
cout<<Ans[x]<<"\n";
}
return 0;
}