QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#776832 | #9529. Farm Management | uglasses | WA | 1ms | 5700kb | C++14 | 1.4kb | 2024-11-23 21:08:50 | 2024-11-23 21:08:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=100055;
ll n,m;
ll ans1,ans2;
ll Rsum[M],Rsumval[M],Lsum[M],Lsumval[M];
ll tmp[M];
struct node
{
ll w,l,r;
}crop[M];
bool cmp(node a,node b)
{
return a.w<b.w;
}
int main()
{
cin>>n>>m;
for(int i=1,a,b,c;i<=n;i++)
{
cin>>a>>b>>c;
crop[i]=(node){a,b,c};
}
sort(crop+1,crop+1+n,cmp);
for(int i=n;i>=1;i--)
{
Rsum[i]=Rsum[i+1]+crop[i].r;
Rsumval[i]=Rsumval[i+1]+crop[i].r*crop[i].w;
}
for(int i=1;i<=n;i++)
{
Lsum[i]=Lsum[i-1]+crop[i].l;
Lsumval[i]=Lsumval[i-1]+crop[i].l*crop[i].w;
}
ans1=Lsumval[n-1]+(m-Lsum[n-1])*crop[n].w;
// cout<<ans1<<endl;
for(int i=1;i<=n;i++)
{
// cout<<Lsum[i-1]+Rsum[i+1]<<"\n";
tmp[i]=m-Lsum[i-1]-Rsum[i+1];
}
for(int i=1;i<=n;i++)
{
ll ans2=0;
if(tmp[i]>=0)
{
ans2+=Lsumval[i-1]+Rsumval[i+1];
ans2+=tmp[i]*crop[i].w;
}
else
{
for(int j=n;j>=i+1;j--)
{
if(Lsum[j]+Rsum[j+1]-crop[i].l>m)
{
ans2=Lsumval[j]+Rsumval[j+2]+(m-(Lsum[j]+Rsum[j+2]-crop[i].l))*crop[j].w;
}
}
}
ans1=max(ans1,ans2);
}
cout<<ans1;
return 0;
}
/*
5 17
2 3 4
6 1 5
8 2 4
4 3 3
7 5 5
5 17
2 2 3
4 12 14
6 1 9
8 1 8
10 1 10
5 17
2 3 4
4 3 3
6 1 5
7 5 5
8 2 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5700kb
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: 3628kb
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:
42448989
result:
wrong answer 1st lines differ - expected: '35204500', found: '42448989'