QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#754977 | #9529. Farm Management | qcfff# | WA | 1ms | 5676kb | C++11 | 1.3kb | 2024-11-16 16:10:54 | 2024-11-16 16:10:56 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m;
struct node{
int val,l,r;
}a[N];
int sl[N],sr[N],vl[N],vr[N];
signed main(){
cin>>n>>m;
int tot=0,sum=0;
for(int i=1;i<=n;i++){
cin>>a[i].val>>a[i].l>>a[i].r;
tot+=a[i].l;
sum+=a[i].l*a[i].val;
}
sort(a+1,a+1+n,[](node x,node y){
return x.val>y.val;
});
for(int i=1;i<=n;i++){
sl[i]=sl[i-1]+a[i].r;
vl[i]=vl[i-1]+a[i].r*a[i].val;
}
for(int i=n;i>=1;i--){
sr[i]=sr[i+1]+a[i].l;
vr[i]=vr[i+1]+a[i].l*a[i].val;
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,sum+a[i].val*(m-tot));
}
for(int i=1;i<=n;i++){
int l=1,r=n-1;
while(l<r){
int mid=(l+r+1)>>1;
int tmp=0;
if(mid>=i){
tmp=sl[mid+1]-a[i].r+sr[mid+2];
}else{
tmp=sl[mid]+sr[mid+1]-a[i].l;
}
if(tmp<=m){
l=mid;
}else{
r=mid-1;
}
}
int tmp=0,vv=0;
if(l>=i){
tmp=sl[l+1]-a[i].r+sr[l+2];
vv=vl[l+1]-a[i].r*a[i].val+vr[l+2];
if(l==n-1||l==i-1){
vv+=(m-tmp)*a[i].val;
}else{
vv+=(m-tmp)*a[l+2].val;
}
}else{
tmp=sl[l]+sr[l+1]-a[i].l;
vv=vl[l]+vr[l+1]-a[i].l*a[i].val;
if(l==n-1||l==i-1){
vv+=(m-tmp)*a[i].val;
}else{
vv+=(m-tmp)*a[l+1].val;
}
}
ans=max(ans,vv);
}
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5632kb
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: 5676kb
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:
35309054
result:
wrong answer 1st lines differ - expected: '35204500', found: '35309054'