QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#748608 | #9529. Farm Management | legohu | WA | 0ms | 7784kb | C++20 | 1.3kb | 2024-11-14 20:50:48 | 2024-11-14 20:50:49 |
Judging History
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'