题解：

貌似一眼看过去是一个贪心。

其他的算法要记录的东西就太多了。

部分分其实很高。但是没有什么提示。

想一些套路：二分？不行还要贪心判断。

分治？前后取法是有影响的。

时光倒流？

也许可以？

其实比较麻烦的是蔬菜变质。这样就使得我们不能每次卖最贵的。

如果时光倒流，那么就会有些蔬菜在某一个时刻以某一个初值出现，然后每过一天，增长固定的个数。

那么，面对最后一天，我们就剩下这么多的菜了。肯定要卖最贵的m个

然后，倒数第二天，一些蔬菜出现了，一些蔬菜变多了，我们在最后一天卖菜的基础上，可以继续选择最贵的m个。

因为，最后一天的菜和倒数第二天的菜交换一定不优，因为可能倒数第二天能买到的，最后一天就坏了。而由于取最大的m个，某天卖其他的菜也不会更优。

类似数学归纳法可以证明。

 

现在我们可以找出来p天的最大收益了。

但是，询问太多了， 可以不可以递推呢？

可以。

求出max(pi)的值mxans

然后，每往前提一天，那么，就把所有卖过的菜中，删掉最便宜的m个。

合法显然，因为后面能卖的，前面一定能卖、

如果不卖这些，同层之间交换不优的。

离线处理，然后倒序递推即可。

细节比较多：

1.不能除以0

2.等等

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize"Ofast"#include
     
      #define ri register int using namespace std;#define int long long#define numb (ch^'0')typedef long long ll;const int N=2e5+5;void rd(int &x){    char ch;x=0;    while(!isdigit(ch=getchar()));    for(x=numb;isdigit(ch=getchar());x=(x<<1)+(x<<3)+numb);}struct node{    ll val;    int id;    int sold;    bool friend operator <(node a,node b){        return a.val
      
       q1;struct bac{    ll val;    ll sum;    bool friend operator <(bac a,bac b){        return a.val>b.val;    }};priority_queue
       
        q2;int n,m,k;struct question{    int day;    int id;    bool friend operator<(question a,question b){        return a.day>b.day;    }}que[N];ll ans[N];int up;int id[N];vector
        
         mem[N];//appear daybool cmp(int a,int b){    return val[a]>val[b];}signed main(){    rd(n);rd(m);rd(k);    bool fl=true;    for(ri i=1;i<=n;i++){        rd(val[i]),rd(s[i]),rd(c[i]),rd(dele[i]);        if(dele[i]) fl=false;    }    for(int i=1;i<=k;i++){        rd(que[i].day);        //scanf("%d",&que[i].day);        que[i].id=i;    }sort(que+1,que+k+1);    up=que[1].day;    //cout<
         
          <
          
           up) app[i+n]=up; rem[i+n]=1; dele[i+n]=0; c[i+n]=1; val[i+n]=s[i]+val[i]; mem[app[i+n]].push_back(i+n); c[i]--; if(c[i]==0) continue;//warning!! int exi=(c[i]+dele[i]-1)/dele[i]; int re=c[i]%dele[i]; if(re==0) re=dele[i]; if(exi>up){ re+=(exi-up)*dele[i]; exi=up; } app[i]=exi,rem[i]=re; mem[exi].push_back(i); } //for(int i=1;i<=2*n;i++){ /// cout<
           <<" : "<
            
             <<" "<
             
              <<" "<
              
               <<" "<
               
                <
                
                 =1;i--){ for(ri j=0;j
                 
                  nd){ now.sold+=nd; mxans+=val[now.id]*nd; sell[now.id]+=nd; nd=0; } else{ now.sold+=has; mxans+=val[now.id]*has; sell[now.id]+=has; nd-=has; } if(now.id<=n) sta[++top]=now;//warning!! id>n not push back } while(top){ q1.push(sta[top]);top--; } //cout<<" after "<
                  <<" : "<
                   
                    <
                    
                     =1;i--){ while(ptr<=k&&que[ptr].day==i){ ans[que[ptr].id]=mxans;ptr++; } if((i-1)*m>=tot) continue;//warning!!! if(i==1) break; int nd=min(m,tot-((i-1)*m)); while(nd){ if(q2.empty()) break; bac now=q2.top();q2.pop(); if(now.sum>nd){ now.sum-=nd; mxans-=nd*now.val; nd=0; q2.push(now); } else{ mxans-=now.sum*now.val; nd-=now.sum; } } } for(int i=1;i<=k;i++){ printf("%lld\n",ans[i]); } return 0;}/* Author: *Miracle* Date: 2018/10/14 14:19:49*/