QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#729660 | #9529. Farm Management | DBsoleil# | WA | 1ms | 9916kb | C++23 | 903b | 2024-11-09 17:34:50 | 2024-11-09 17:34:52 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
ll n,m;
ll w[N],l[N],r[N],ans,sval[N],snum[N];
int main(){
cin>>n>>m;
ll sum=0,num=0;
for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&w[i],&l[i],&r[i]),sum+=w[i]*l[i],num+=l[i];
for(int i=n;i>=1;i--)sval[i]=sval[i+1]+w[i]*(r[i]-l[i]),snum[i]=snum[i+1]+r[i]-l[i];
for(int i=1;i<=n;i++){
ll res=sum-w[i]*l[i],last=m-num+l[i];
int L=i+1,R=n,mid,pre=i+1;
while(L<=R){
mid=(L+R)>>1;
if(snum[mid]<=last)pre=mid,R=mid-1;
else L=mid+1;
}
if(pre==i+1){
res+=sval[pre];
last-=snum[pre];
res+=last*w[i];
}else{
res+=sval[pre];
last-=snum[pre];
res+=last*w[pre-1];
}
ans=max(ans,res);
}
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9860kb
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: 9916kb
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:
34616000
result:
wrong answer 1st lines differ - expected: '35204500', found: '34616000'