提交记录 13260


用户 题目 状态 得分 用时 内存 语言 代码长度
lhm_ noi17e. 【NOI2017】蔬菜 Accepted 100 84.301 ms 13216 KB C++ 2.26 KB
提交时间 评测时间
2020-08-01 08:59:08 2020-08-01 08:59:14
#include<bits/stdc++.h>
#define maxn 100010
#define all 100000LL
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
ll n,m,k,top,tot;
ll a[maxn],s[maxn],c[maxn],d[maxn],num[maxn],ans[maxn];
bool vis[maxn];
struct node
{
    ll v,id;
}st[maxn];
bool operator <(const node &a,const node &b)
{
    return a.v<b.v;
}
vector<int> ve[maxn];
priority_queue<node> q;
int main()
{
    read(n),read(m),read(k);
    for(int i=1;i<=n;++i)
    {
        read(a[i]),read(s[i]),read(c[i]),read(d[i]);
        if(!d[i]) ve[all].push_back(i);
        else ve[min(all,(c[i]+d[i]-1)/d[i])].push_back(i);
    }
    for(int i=all;i;--i)
    {
        ll now=m;
        for(int j=0;j<ve[i].size();++j)
            q.push((node){a[ve[i][j]]+s[ve[i][j]],ve[i][j]});
        while(!q.empty()&&now)
        {
            node x=q.top();
            q.pop();
            if(!vis[x.id])
            {
                vis[x.id]=true,ans[all]+=x.v,num[x.id]++,now--;
                if(c[x.id]!=1) q.push((node){a[x.id],x.id});
            }
            else
            {
                ll val=min(now,c[x.id]-num[x.id]-(i-1)*d[x.id]);
                ans[all]+=x.v*val,num[x.id]+=val,now-=val;
                if(c[x.id]!=num[x.id]) st[++top]=(node){a[x.id],x.id};
            }
        }
        while(top) q.push(st[top--]);
    }
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;++i)
    {
        if(!num[i]) continue;
        tot+=num[i];
        if(num[i]==1) q.push((node){-a[i]-s[i],i});
        else q.push((node){-a[i],i});
    }
    for(int i=all-1;i;--i)
    {
        ans[i]=ans[i+1];
        while(!q.empty()&&tot>i*m)
        {
            node x=q.top();
            q.pop(),x.v*=-1;
            if(num[x.id]==1) ans[i]-=x.v,num[x.id]--,tot--;
            else
            {
                ll val=min(num[x.id]-1,tot-i*m);
                ans[i]-=x.v*val,num[x.id]-=val,tot-=val;
                if(num[x.id]==1) q.push((node){-a[x.id]-s[x.id],x.id});
                else q.push((node){-a[x.id],x.id});
            }
        }
    }
    for(int i=1,p;i<=k;++i) read(p),printf("%lld\n",ans[p]);
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #11.019 ms3 MB + 124 KBAcceptedScore: 4

Testcase #21.054 ms3 MB + 128 KBAcceptedScore: 4

Testcase #31.039 ms3 MB + 128 KBAcceptedScore: 4

Testcase #4972.06 us3 MB + 200 KBAcceptedScore: 4

Testcase #5970.79 us3 MB + 200 KBAcceptedScore: 4

Testcase #6976.22 us3 MB + 200 KBAcceptedScore: 4

Testcase #7801.58 us3 MB + 116 KBAcceptedScore: 4

Testcase #8800.34 us3 MB + 116 KBAcceptedScore: 4

Testcase #9804.38 us3 MB + 116 KBAcceptedScore: 4

Testcase #10782.93 us3 MB + 116 KBAcceptedScore: 4

Testcase #11812.25 us3 MB + 120 KBAcceptedScore: 4

Testcase #12843.4 us3 MB + 128 KBAcceptedScore: 4

Testcase #13854.65 us3 MB + 124 KBAcceptedScore: 4

Testcase #14867.91 us3 MB + 128 KBAcceptedScore: 4

Testcase #15846.12 us3 MB + 128 KBAcceptedScore: 4

Testcase #161.351 ms3 MB + 208 KBAcceptedScore: 4

Testcase #171.427 ms3 MB + 224 KBAcceptedScore: 4

Testcase #181.405 ms3 MB + 208 KBAcceptedScore: 4

Testcase #191.467 ms3 MB + 224 KBAcceptedScore: 4

Testcase #201.469 ms3 MB + 224 KBAcceptedScore: 4

Testcase #2175.831 ms12 MB + 436 KBAcceptedScore: 4

Testcase #2250.94 ms12 MB + 548 KBAcceptedScore: 4

Testcase #2384.301 ms12 MB + 440 KBAcceptedScore: 4

Testcase #2455.312 ms12 MB + 924 KBAcceptedScore: 4

Testcase #2555.637 ms12 MB + 928 KBAcceptedScore: 4


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