QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#776827#9529. Farm ManagementuglassesRE 0ms3552kbC++141.4kb2024-11-23 21:06:582024-11-23 21:06:58

Judging History

你现在查看的是最新测评结果

  • [2024-11-23 21:06:58]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3552kb
  • [2024-11-23 21:06:58]
  • 提交

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: 0ms
memory: 3552kb

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
Runtime Error

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:


result: