QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#716926 | #9529. Farm Management | EDGE | WA | 0ms | 3704kb | C++20 | 1.9kb | 2024-11-06 16:24:08 | 2024-11-06 16:24:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10;
struct node{
ll v;
ll l,r,t,sl,sr,lt,rt;
}e[maxn];
bool cmp(node x,node y){return x.v<y.v;}
int n,md;
ll m,now=0,ans=0;
bool check(int i,int tp){
if(e[i].rt<tp) return false;
return true;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
ll r=m;
for(int i=1;i<=n;i++){
cin>>e[i].v>>e[i].l>>e[i].r;
}
sort(e+1,e+1+n,cmp);
for(int i=1;i<=n;i++){
r-=e[i].l;
e[i].t=e[i].l;
}
for(int i=n;i>=1;i--){
if(r>=e[i].r-e[i].l){
r-=e[i].r-e[i].l;
e[i].t=e[i].r;
}
else {
e[i].t+=r;
md=i;break;
}
}
r=m;
for(int i=1;i<=n;i++) ans+=e[i].v*e[i].t;
//cout<<ans<<"\n";
for(int i=1;i<=n;i++) {e[i].sl=e[i-1].sl+e[i].v*e[i].l;}//cout<<e[i].sl<<" ";}cout<<"\n";
for(int i=n;i>=1;i--) {e[i].sr=e[i+1].sr+e[i].v*e[i].r;}//cout<<e[i].sr<<" ";}cout<<"\n";
for(int i=1;i<=n;i++) {e[i].lt=e[i-1].lt+e[i].t-e[i].l;}//cout<<e[i].lt<<" ";}cout<<"\n";
for(int i=n;i>=1;i--) {e[i].rt=e[i+1].rt+e[i].r-e[i].t;}//cout<<e[i].rt<<" ";}cout<<"\n";
for(int i=1;i<=n;i++){
if(md<i){
now=e[i-1].lt*e[i].v+e[i+1].sr+e[i-1].sl;
ans=max(ans,now);
}
else if(i<md){
ll tp=e[i].t;
if(e[i+1].rt<=tp) now=(tp-e[i+1].rt)*e[i].v+e[i-1].sl+e[i+1].sr;
else{
int L=i+1,R=md,j;
while(L<R){
int mid=(L+R)>>1;
if(check(mid,tp)){L=mid+1;j=mid;}
else {R=mid-1;}
}
now=(tp-e[j+1].rt)*e[j].v+e[j-1].sl+e[j+1].sr;
}
ans=max(now,ans);
}
}
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
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: 3704kb
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:
36232275
result:
wrong answer 1st lines differ - expected: '35204500', found: '36232275'