QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#718643 | #9529. Farm Management | Exile_Code# | WA | 1ms | 3860kb | C++20 | 1.8kb | 2024-11-06 21:02:06 | 2024-11-06 21:02:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define endl '\n'
#define vv vector
#define all(x) x.begin()+1,x.end()
#define int ll
#define ft first
#define sd second
struct node
{
int w,l,r;
int rest;
node(int w_=0,int l_=0,int r_=0,int rest_=0):w(w_),l(l_),r(r_),rest(rest_) {}
friend bool operator<(const node&a,const node&b)
{
return a.w>b.w;
};
};
void solve(){
int n,m;
cin>>n>>m;
vector<node> a(n+1);
ll sumL=0;
ll sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i].w>>a[i].l>>a[i].r;
sumL+=a[i].l;
sum+=a[i].l*a[i].w;
a[i].rest=a[i].r-a[i].l;
}
sort(a.begin()+1,a.end());
ll now=sumL;
for(int i=1;i<=n;i++)
{
if(a[i].rest+now<m)
{
a[i].rest=0;
sum+=a[i].rest*a[i].w;
}
else
{
a[i].rest-=m-now;
sum+=(m-now)*a[i].w;
now=m;
break;
}
}
vector<int> preR(n+1);
for(int i=1;i<=n;i++)
{
preR[i]=preR[i-1]+a[i].rest;
}
vector<int> preW(n+1);
for(int i=1;i<=n;i++)
{
preW[i]=preW[i-1]+(a[i].r-a[i].rest)*a[i].w;
}
ll ans=preW[n];
for(int i=1;i<=n;i++)
{
int re=a[i].rest;
preR[i]+=m-re;
int l=1,r=i;
while (l<r)
{
int mid=(l+r+1)>>1;
if(preR[mid]>re)
r=mid-1;
else
l=mid;
}
ans=max(ans,preW[l-1]+(re-preR[l-1])*a[l].w);
preR[i]-=m-re;
}
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _=1;
// cin>>_;
while(_--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
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: 3860kb
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:
31758380
result:
wrong answer 1st lines differ - expected: '35204500', found: '31758380'