QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#717205 | #9529. Farm Management | EDGE | WA | 0ms | 3608kb | C++20 | 2.0kb | 2024-11-06 17:13:42 | 2024-11-06 17:13:44 |
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,rl;
}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++) {e[i].rl=e[i-1].rl+e[i].v*e[i].t;}
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;
//cout<<tp<<" "<<i<<"\n";
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=L;
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].t)*e[j].v+e[j-1].rl+e[j+1].sr-e[i].v*e[i].t;
//cout<<now<<"\n";
}
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: 3560kb
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: 0
Accepted
time: 0ms
memory: 3608kb
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:
35204500
result:
ok single line: '35204500'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3580kb
input:
15 32 835418 2 3 178262 1 3 527643 2 2 519710 1 1 774544 3 3 82312 1 1 808199 1 1 809396 1 3 255882 1 3 80467 1 3 874973 1 3 813965 1 2 198275 1 2 152356 1 3 802055 1 1
output:
20492921
result:
wrong answer 1st lines differ - expected: '22000255', found: '20492921'