QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#748608#9529. Farm ManagementlegohuWA 0ms7784kbC++201.3kb2024-11-14 20:50:482024-11-14 20:50:49

Judging History

你现在查看的是最新测评结果

  • [2024-11-14 20:50:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7784kb
  • [2024-11-14 20:50:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
struct node{
    ll w,l,r,id;
    node(){}
    node(ll W,ll L,ll R,ll ID){
        w=W;l=L;r=R;id=ID;
    }
    friend bool operator<(const node&x,const node&y){
        return x.w>y.w;
    }
}a[N],b[N];int cur=1,usd=0;
bool cmp(const node&x,const node&y){return x.l<y.l;}
ll gnew(int m){
    ll sum=0;//cout<<m;
    while(b[cur].r<usd+m){
        m-=b[cur].r-usd;
        sum+=(b[cur].r-usd)*b[cur].w;
        usd=0;cur++;
    }
    sum+=m*b[cur].w;usd=m;
    //cout<<" left with sum"<<sum<<endl;
    return sum;
}
ll n,m,w[N],l[N],r[N],p;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%lld %lld %lld",&w[i],&l[i],&r[i]);
        if(w[p]<w[i])p=i;
        if(w[p]==w[i]&&r[i]>r[p])p=i;
        a[i]=node(w[i],l[i],r[i],i);
    }
    ll sum=0,len=0,ans=0,ml=0;
    for(int i=1;i<=n;i++)
    {
        sum+=l[i]*w[i];len+=l[i];
        b[i]=a[i];b[i].r-=b[i].l;
    }
    sort(a+1,a+1+n,cmp);sort(b+1,b+1+n);
    ans=sum-l[p]*w[p]+(m-len+l[p])*w[p];
    sum+=gnew(m-len);a[0].l=0;
    ans=max(sum,ans);
    for(int i=1;i<=n;i++){
        sum+=gnew(a[i].l-a[i-1].l);
        ans=max(ans,sum-a[i].l*a[i].w);
    }
    cout<<ans<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7784kb

input:

5 17
2 3 4
6 1 5
8 2 4
4 3 3
7 5 5

output:

109

result:

ok single line: '109'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 7708kb

input:

12 62
503792 9 10
607358 1 3
600501 10 10
33249 4 4
774438 6 6
197692 3 6
495807 8 8
790225 5 9
77272 3 8
494819 4 9
894779 3 9
306279 5 6

output:

35277263

result:

wrong answer 1st lines differ - expected: '35204500', found: '35277263'