代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<iostream>
# define int long long
const int M = 500005 ;
const int INF = 1e18 ;
using namespace std ;
inline int read(){
    char c = getchar() ; int x = 0 , w = 1 ;
    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
    while(c>='0'&&c<='9'){ x = x*10+c - '0' ; c = getchar() ; }
    return x*w ;
}
int n , m , T ;
int a[M] , s[M] , x[M] , c[M] ;
struct Node{
    int Res , val , id ; bool Isfirst ;
    inline friend bool operator < (Node a , Node b){
        return a.val < b.val ;
    }
};
struct Vegetable{
    int a , s , c , x , upp ;
    inline friend bool operator < (Vegetable a , Vegetable b){
        return a.upp > b.upp ;
    }
}v[M];
int tag[M] , tnum ;
priority_queue<Node>q;
Node u ;
bool f ;
Node temp[105] ;
inline bool Deal(int k){
    if(u.Res) {
        f = 1 ;
        return true ;
    }
    int i = u.id ;
    if(tag[i] == k) return false ;
    f = 1 ;
    u.Res += (tag[i] - k) * v[i].x ;
    tag[i] = k ;
    return true ;
}
inline int Solve(int k){
    while(!q.empty()) q.pop() ;
    memset(tag , 0 , sizeof(tag)) ;
    int Ans = 0 , now = 1 ;
    for(int i=k;i>=1;i--){
        for(int j=now;j<=n;j++)
            if(v[j].upp >= i){
          	    if(j == n) now = INF ;
          	    tag[j] = i ;
                q.push((Node){1 , v[j].a + v[j].s , j , true }) ;
                q.push((Node){v[j].c - (i - 1) * v[j].x - 1 , v[j].a , j , false }) ; 
            }
            else{
          	    now = j ;
          	    break ;
            }
        int num = m ;
        tnum = 0 ;
        while(num && !q.empty()){
            Node u = q.top() ; q.pop() ;
            if(u.Isfirst){
                --num ;
                Ans += u.val ;
                continue ;
            }
            else{
                int x = u.id ;
                u.Res += (tag[x] - i) * v[x].x ;
                tag[x] = i ;
                if(u.Res <= num){
                    Ans += u.val * u.Res ;
                    num -= u.Res ;
                    u.Res = 0 ;
                }
                else{
                    Ans += u.val * num ;
                    u.Res -= num ;
                    num = 0 ;
                }
                temp[++tnum] = u ;
            }
        }
        for(int j=1;j<=tnum;j++) q.push(temp[j]) ;
    }
    return Ans ;
}
# undef int
int main(){
# define int long long
    n = read() ; m = read() ; T = read() ;
    for(int i=1;i<=n;i++){
        v[i].a = read() ; v[i].s = read() ;
        v[i].c = read() ; v[i].x = read() ;
        if(v[i].x == 0) v[i].upp = INF ; 
        else v[i].upp = ceil((double)v[i].c/v[i].x) ;   	
    }
    sort(v + 1 , v + n + 1) ;
    while(T--){
        int x = read() ;
        printf("%lld\n",Solve(x)) ;
    }
    return 0 ;
}

评测结果