QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#678615#9529. Farm Managementucup-team3661#WA 0ms3732kbC++201.6kb2024-10-26 15:32:442024-10-26 15:32:45

Judging History

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

  • [2024-10-26 15:32:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3732kb
  • [2024-10-26 15:32:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
	ll N,M;cin>>N>>M;
	vector<tuple<ll,ll,ll>>W(N);
	for(auto&[w,l,r]:W)cin>>w>>l>>r;
	sort(W.rbegin(),W.rend());

	vector<ll>use(N),rem(N);
	ll rem_time=M,tmp_val=0;
	for(int i=0;i<N;i++){
		auto[w,l,r]=W[i];
		tmp_val+=l*w;
		use[i]=l;
		rem[i]=r-l;
		rem_time-=use[i];
	}
	for(int i=0;i<N;i++){
		auto[w,l,r]=W[i];
		if(rem[i]<=rem_time){
			tmp_val+=rem[i]*w;
			rem_time-=rem[i];
			use[i]+=rem[i];
			rem[i]=0;
		}else{
			tmp_val+=rem_time*w;
			rem[i]-=rem_time;
			use[i]+=rem_time;
			rem_time=0;
		}
		if(rem_time==0)break;
	}
	assert(rem_time==0);

	vector<ll>pref_rem(N+1),pref_val(N+1);
	for(int i=0;i<N;i++){
		auto[w,l,r]=W[i];
		pref_rem[i+1]=pref_rem[i]+rem[i];
		pref_val[i+1]=pref_val[i]+rem[i]*w;
	}

	ll ans=tmp_val;
	for(int i=0;i<N;i++){
		auto[w,l,r]=W[i];
		if(rem[i]==0)continue;

		//使う時間を0にする
		ll new_rem=use[i];
		ll res=tmp_val-use[i]*w;
		//これを上から分配する
		int lo=-1,hi=i+1;
		while(hi-lo>1){
			int mid=(hi+lo)/2;
			if(pref_rem[mid]<=new_rem)lo=mid;
			else hi=mid;
		}
		ll new_rem2=new_rem-pref_rem[lo];
		assert(new_rem2>=0);
		res+=pref_val[lo];
		//余った時間をloに割り当てる
		res+=new_rem2*get<0>(W[lo]);
		if(lo<i)assert(new_rem2<=rem[lo]);
		ans=max(ans,res);
	}

	{
		ll res=0;
		ll rem_time=M;
		for(int i=1;i<N;i++){
			auto[w,l,r]=W[i];
			res+=l*w;
			rem_time-=l;
		}
		{
			auto[w,l,r]=W[0];
			res+=rem_time*w;
		}
		ans=max(ans,res);
	}

	cout<<ans<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3452kb

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: 3732kb

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:

34859047

result:

wrong answer 1st lines differ - expected: '35204500', found: '34859047'