提交记录 6603


用户 题目 状态 得分 用时 内存 语言 代码长度
FlashHu noi17e. 【NOI2017】蔬菜 Accepted 100 45.349 ms 16268 KB C++ 1.40 KB
提交时间 评测时间
2018-10-30 16:53:52 2020-08-01 00:46:39
#include<bits/stdc++.h>
#define LL long long
#define RG register
#define R RG int
#define G if(++ip==ie)fread(ip=buf,1,N,stdin)
using namespace std;
const int N=2e5+9,M=1e6+9;
char buf[N],*ie=buf+N,*ip=ie-1;
int p[N],f[M];LL ans[M];
inline int in(){
    G;while(*ip<'-')G;
    R x=*ip&15;G;
    while(*ip>'-'){x*=10;x+=*ip&15;G;}
    return x;
}
struct Veg{
    int a,c,x;
    inline bool operator<(RG Veg&b){
        return a>b.a;
    }
}v[N];
int getf(R x){
    return x==f[x]?x:f[x]=getf(f[x]);
}
int main(){
    R n=in(),m=in(),k=in(),i,l=0;
    for(i=1;i<=n;++i){
        v[i].a=in();v[i+n].a=v[i].a+in();
        v[i].c=in()-1;v[i+n].c=1;
        if((v[i].x=in()))v[i+n].x=-(v[i].c/v[i].x+1);
    }
    for(i=1;i<=k;++i)l=max(l,p[i]=in());
    R tot=l*m,j=1,t=0,x;
    for(i=1;i<=tot;++i)f[i]=i;
    sort(v+1,v+(n*=2)+1);
    for(i=1;i<=n;++i){
        //printf("a%d c%d x%d\n",v[i].a,v[i].c,v[i].x);
        while(v[i].c){
            --v[i].c;
            x=v[i].x==0?tot:min((v[i].x>0?(v[i].c/v[i].x+1):-v[i].x)*m,tot);
            //printf("x%d ",x);
            x=getf(x);
            //printf("f%d\n",x);
            if(!x)break;
            //puts("get");
            --f[f[x]];ans[j]+=v[i].a;
            if(++t==m){
                if(++j>tot)goto F;
                t=0;ans[j]=ans[j-1];
            }
        }
    }
  F:for(++j;j<=tot;++j)ans[j]=ans[j-1];
    for(i=1;i<=k;++i)printf("%lld\n",ans[p[i]]);
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1272.66 us184 KBAcceptedScore: 4

Testcase #2330.37 us188 KBAcceptedScore: 4

Testcase #3312.82 us188 KBAcceptedScore: 4

Testcase #4156.74 us104 KBAcceptedScore: 4

Testcase #5156.35 us104 KBAcceptedScore: 4

Testcase #6158.45 us104 KBAcceptedScore: 4

Testcase #738.89 us56 KBAcceptedScore: 4

Testcase #840.49 us56 KBAcceptedScore: 4

Testcase #938.53 us56 KBAcceptedScore: 4

Testcase #1039.11 us56 KBAcceptedScore: 4

Testcase #1150.45 us56 KBAcceptedScore: 4

Testcase #1282.5 us68 KBAcceptedScore: 4

Testcase #1376.06 us68 KBAcceptedScore: 4

Testcase #1483.84 us72 KBAcceptedScore: 4

Testcase #1585.63 us72 KBAcceptedScore: 4

Testcase #16421.33 us228 KBAcceptedScore: 4

Testcase #17517.68 us228 KBAcceptedScore: 4

Testcase #18435.96 us236 KBAcceptedScore: 4

Testcase #19541.45 us236 KBAcceptedScore: 4

Testcase #20544.19 us240 KBAcceptedScore: 4

Testcase #2144.476 ms15 MB + 868 KBAcceptedScore: 4

Testcase #2243.293 ms15 MB + 908 KBAcceptedScore: 4

Testcase #2345.349 ms15 MB + 872 KBAcceptedScore: 4

Testcase #2444.827 ms15 MB + 880 KBAcceptedScore: 4

Testcase #2544.984 ms15 MB + 876 KBAcceptedScore: 4


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