QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#717232 | #9529. Farm Management | zhensama | WA | 0ms | 3828kb | C++20 | 1.3kb | 2024-11-06 17:17:55 | 2024-11-06 17:17:56 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=1e5+10;
struct node
{
int w,l,r,sum,diff,Sum;
}a[N];
bool cmp(node a,node b)
{
return a.w>b.w||a.w==b.w&&a.l<b.l;
}
void solve()
{
int n,m;cin>>n>>m;
int L[n+1]={0},R[n+1]={0},S=0;
for(int i=1;i<=n;i++)
{
cin>>a[i].w>>a[i].l>>a[i].r;
a[i].sum=a[i].w*a[i].l;
a[i].diff=a[i].r-a[i].l;
a[i].Sum=a[i].diff*a[i].w;
S+=a[i].sum;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
L[i]=L[i-1]+a[i].l;
R[i]=R[i-1]+a[i].r;
}
//cout<<L[n]<<" "<<R[n]<<'\n';
vector<int> diff(n+10,0),Sum(n+10,0);
for(int i=1;i<=n;i++)
{
diff[i]=diff[i-1]+a[i].diff;
Sum[i]=Sum[i-1]+a[i].Sum;
}
int sum=0;
for(int i=1;i<=n;i++)
{
int ans=S;
int t=L[n];
ans-=a[i].sum;
t-=a[i].l;
int bin=upper_bound(diff.begin(),diff.begin()+i-1,m-t)-diff.begin();
//cout<<bin<<" ";
ans+=Sum[bin]+a[bin+1].w*(m-t-diff[bin]);
//cout<<ans<<" ";
sum=max(sum,ans);
}
cout<<sum<<'\n';
}
signed main()
{
ios::sync_with_stdio(0);
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: 0ms
memory: 3548kb
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: 3828kb
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:
35309054
result:
wrong answer 1st lines differ - expected: '35204500', found: '35309054'