QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#717817 | #9529. Farm Management | 20225954# | WA | 1ms | 5784kb | C++14 | 1.5kb | 2024-11-06 19:01:50 | 2024-11-06 19:01:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define db(x) cerr<<#x<<(x)<<"\n"
#define db1(x) cerr<<#x<<(x)<<" "
#define rep(i,a,b) for(auto i=(a);i<=(b);i++)
#define ll long long
const int N = 1e5+10;
ll n,m,sw;
ll suf[N],pre[N],prew[N],sufw[N],ans,tmpans,suml;
struct st{
ll l,r,w;
bool operator<(const st& T)const{
return w<T.w;
}
};
st a[N];
int main()
{
cin>>n>>m;
rep(i,1,n){
cin>>a[i].w>>a[i].l>>a[i].r;
suml+=a[i].l;
sw+=(a[i].l)*a[i].w;
}
sort(a+1,a+1+n);
for(int i=n;i>=1;i--){
suf[i] = suf[i+1]+a[i].r-a[i].l;
sufw[i] = sufw[i+1]+(a[i].w)*(a[i].r-a[i].l);
}
rep(i,1,n){
prew[i] = prew[i-1]+(a[i].w)*(a[i].l);
pre[i] = pre[i-1]+a[i].l;
// cout<<a[i].w<<" "<<a[i].l<<" "<<a[i].r<<"\n";
}
// rep(i,1,n){
// db(i),db(pre[i]);
// }
for(int i=1;i<=n;i++){
ll nsum = m-(suml-a[i].l);
// db1(i),db(nsum);
int l = i-1,r =n+1;
while(l+1<r){
int mid = (l+r)>>1;
if(suf[mid]<=nsum){
r = mid;
}else l = mid;
}
//答案是r 的位置但是还剩下一些
ll recnt = nsum-suf[r];
tmpans = 0;
if(recnt!=0){
tmpans = tmpans+a[r-1].w*recnt;
}
tmpans +=(sufw[r]+sw-(a[i].l)*a[i].w);
// if(tmpans>ans){
// cout<<"i======="<<i<<"\n";
// }
ans = max(ans,tmpans);
}
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5676kb
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: 1ms
memory: 5628kb
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: 1ms
memory: 5784kb
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:
21525595
result:
wrong answer 1st lines differ - expected: '22000255', found: '21525595'