QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#727274 | #9529. Farm Management | xuzhihaodedie | WA | 1ms | 7700kb | C++14 | 1.6kb | 2024-11-09 12:26:14 | 2024-11-09 12:26:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y second
#define PII pair<int,int>
//#define endl "\n"
#define lson 2*p
#define rson 2*p+1
const int N=2e5+10;
const int mod=998244353;
int l[N],r[N],w[N],id[N];
bool cmp(int x,int y) {
return w[x]<w[y];
}
void solve() {
int n,m;
cin>>n>>m;
int res=0,ans=0;
int remain=m;
for(int i=1;i<=n;i++) {
cin>>w[i]>>l[i]>>r[i],res+=l[i]*w[i];
remain-=l[i];
id[i]=i;
}
sort(id+1,id+n+1,cmp);
vector<int> pre(n+10,0),suf(n+10,0);
vector<int> sufval(n+10,0);
for(int i=1;i<=n;i++) {
int p=id[i];
pre[i]=pre[i-1]+r[p]-l[p];
}
for(int i=n;i>=1;i--) {
int p=id[i];
suf[i]=suf[i+1]+r[p]-l[p];
sufval[i]=sufval[i+1]+(r[p]-l[p])*w[p];
}
for(int i=1;i<=n;i++) {
int j=id[i];
remain+=l[j];
int ret=res-l[j]*w[j];
int L=1,R=n,req=0;
while(L<=R) {
int mid=L+R>>1;
int val=suf[mid];
if(mid<=i) val=val+m-r[j];
if(remain>=val) req=mid,R=mid-1;
else L=mid+1;
}
if(!req) {
ans=max(ans,ret+(remain)*w[id[n]]);
} else {
ret+=sufval[req];
int val=suf[req];
if(req<=i) val+=m-r[j],ret+=w[j]*(m-r[j])+l[j]*w[j];
if(req>1) {
req--;
int remain1=remain-val;
remain1=max(0ll,remain1);
if(req==i) {
ret+=min(remain1,m-(r[j]-l[j]))*w[j];
} else {
j=id[req];
ret+=min(remain1,r[j]-l[j])*w[j];
}
}
ans=max(ans,ret);
}
remain-=l[j];
}
cout<<ans<<endl;
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int T=1;
// cin>>T;
while(T--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7700kb
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: 1ms
memory: 7688kb
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:
36577555
result:
wrong answer 1st lines differ - expected: '35204500', found: '36577555'