提交记录 5944


用户 题目 状态 得分 用时 内存 语言 代码长度
greatinfluence noi17e. 【NOI2017】蔬菜 Accepted 100 83.904 ms 11172 KB C++11 3.54 KB
提交时间 评测时间
2018-09-13 16:44:43 2020-08-01 00:37:05
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i)
#define For(i,a,b) for(i=(a),i<=(b);++i)
#define Forward(i,a,b) for(i=(a),i>=(b);--i)
#define Chkmin(a,b) a=a<b?a:b
#define Chkmax(a,b) a=a>b?a:b
#define pb push_back
inline void read(int &x)
{
    static const int BUFSIZE = 1048576;
    static char buf[BUFSIZE];
    static char *bufnow = buf;
    static char *bufmax = buf;
    if (bufnow == bufmax) {
        bufmax = buf + fread(buf, 1, BUFSIZE, stdin);
        bufnow = buf;
    }
    static int c;
    c = *bufnow++;
    for (;!isdigit(c);c = *bufnow++) {
            if (bufnow == bufmax) {
            bufmax = buf + fread(buf, 1, BUFSIZE, stdin);
            bufnow = buf;
        }
    }
    x = 0;
    for (;isdigit(c);c = *bufnow++) {
        x = (x << 1) + (x << 3) + c - 48;
        if (bufnow == bufmax) {
            bufmax = buf + fread(buf, 1, BUFSIZE, stdin);
            bufnow = buf;
        }
    }
}

inline void write(int a,char ed='\n')
{
    static short s[13],tp;
    if(!a){putchar('0'),putchar(ed);return;}
    for(tp=0;a;a/=10)s[++tp]=a%10;
    for(;tp;putchar(s[tp--]^48));
    putchar(ed);
}
using namespace std;
void file()
{
#ifndef ONLINE_JUDGE
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
#endif
}

const int MAXN=1e5+7;

static int n,m,k;

static int a[MAXN],s[MAXN],c[MAXN],x[MAXN];

typedef long long ll;

static int que[MAXN],P;

static vector<int>App[MAXN];

inline void init()
{
    read(n);read(m);read(k);
    Rep(i,1,n)read(a[i]),read(s[i]),read(c[i]),read(x[i]);
    Rep(i,1,k)read(que[i]),Chkmax(P,que[i]);
    Rep(i,1,n)
    {
        if(x[i])App[min(P,(c[i]+x[i]-1)/x[i])].push_back(i);
        else App[P].push_back(i);
    }
}

typedef pair<int,int>Pr;

static priority_queue<Pr>G;

static priority_queue<Pr,vector<Pr>,greater<Pr> >K;

static bool us[MAXN];

static ll ans[MAXN],sold;

static int got[MAXN];

static queue<int>shown;

inline void solve()
{
    static int poi,t;
    static ll an=0ll;
    static int u,v;
    Repe(i,P,1)
    {
        for(int j:App[i])G.push(Pr(a[j]+s[j],j));
        if(G.empty())continue;
        for(poi=m;poi&&!G.empty();G.pop())
        {
            u=G.top().first,v=G.top().second;
            if(!us[v])
            {
                us[v]=true;++got[v];an+=u;--poi;
                if(c[v]>1)G.push(Pr(a[v],v));
            }
            else
            {
                t=min(poi,c[v]-got[v]-(i-1)*x[v]);
                poi-=t;got[v]+=t;an+=(ll)u*t;
                if(got[v]<c[v])shown.push(v);
            }
        }
        for(;!shown.empty();shown.pop())
        {
            u=shown.front();
            G.push(Pr(a[u],u));
        }
    }
    ans[P]=an;
    static long long num=0ll;
    Rep(i,1,n)
    {
        if(got[i]==1)K.push(Pr(a[i]+s[i],i));
        else if(got[i])K.push(Pr(a[i],i));
        sold+=got[i];if(got[i])num+=got[i]*a[i]+s[i];
    }
    Repe(i,P-1,1)
    {
        ans[i]=ans[i+1];
        if(sold<=i*m)continue;
        poi=sold-i*m;
        while(poi)
        {
            u=K.top().first;v=K.top().second;K.pop();
            if(got[v]>1)
            {
                t=min(poi,got[v]-1);
                got[v]-=t;poi-=t;ans[i]-=(ll)t*u;
                if(got[v]==1)K.push(Pr(a[v]+s[v],v));
                else K.push(Pr(u,v));
            }
            else{--poi;--got[v];ans[i]-=u;}
        }sold=m*i;
    }
    Rep(i,1,k)printf("%lld\n",ans[que[i]]);
}

int main()
{
    init();
    solve();
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1568.8 us2 MB + 388 KBAcceptedScore: 4

Testcase #2616.6 us2 MB + 396 KBAcceptedScore: 4

Testcase #3615.61 us2 MB + 396 KBAcceptedScore: 4

Testcase #4422.49 us2 MB + 432 KBAcceptedScore: 4

Testcase #5420.96 us2 MB + 432 KBAcceptedScore: 4

Testcase #6425.71 us2 MB + 432 KBAcceptedScore: 4

Testcase #7355.68 us2 MB + 368 KBAcceptedScore: 4

Testcase #8353.13 us2 MB + 372 KBAcceptedScore: 4

Testcase #9357.1 us2 MB + 372 KBAcceptedScore: 4

Testcase #10357.28 us2 MB + 372 KBAcceptedScore: 4

Testcase #11365.33 us2 MB + 372 KBAcceptedScore: 4

Testcase #12412.39 us2 MB + 372 KBAcceptedScore: 4

Testcase #13408.89 us2 MB + 372 KBAcceptedScore: 4

Testcase #14419.07 us2 MB + 376 KBAcceptedScore: 4

Testcase #15414.41 us2 MB + 372 KBAcceptedScore: 4

Testcase #16939.72 us2 MB + 448 KBAcceptedScore: 4

Testcase #17964.19 us2 MB + 468 KBAcceptedScore: 4

Testcase #18979.14 us2 MB + 460 KBAcceptedScore: 4

Testcase #19999.9 us2 MB + 480 KBAcceptedScore: 4

Testcase #20997.88 us2 MB + 484 KBAcceptedScore: 4

Testcase #2177.477 ms10 MB + 416 KBAcceptedScore: 4

Testcase #2240.25 ms10 MB + 520 KBAcceptedScore: 4

Testcase #2383.904 ms10 MB + 932 KBAcceptedScore: 4

Testcase #2443.647 ms10 MB + 628 KBAcceptedScore: 4

Testcase #2543.822 ms10 MB + 636 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-29 19:52:20 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用