Submission #17247247

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int lim,X,n,b[N],l[N],u[N],a[N];
struct num{
	int b,l,r;
}c[N];
bool cmp(num i,num j){
	return (X-i.b)*i.r+i.b*i.l>(X-j.b)*j.r+j.b*j.l;
}
int calc(int i,int limit){
	if(limit>=c[i].b) return (limit-c[i].b)*c[i].r+c[i].b*c[i].l;
	else return limit*c[i].l;
}
bool check(int limit){
	int pos=limit/X;
	lim=limit%X;
	int ans=0,sum=0;
	for(int i=1;i<=n;++i)
		sum-=b[i]*l[i];
	for(int i=1;i<=pos;++i)
		sum+=calc(i,X);
	ans=sum;
	for(int i=pos+1;i<=n;++i)
		ans=max(ans,sum+calc(i,lim));
	if(pos+1<=n){
		sum+=calc(pos+1,X);
		for(int i=1;i<=pos;++i)
			ans=max(ans,sum-calc(i,X)+calc(i,lim));
	}
	return bool(ans>=0);
}
signed main(){
//	freopen("1_009.txt","r",stdin);
	cin>>n>>X;
	for(int i=1;i<=n;++i)
		cin>>b[i]>>l[i]>>u[i];	
	for(int i=1;i<=n;++i)
		c[i].b=b[i],c[i].l=l[i],c[i].r=u[i];	
	int l=0,r=X*n,ans=X*n;
	sort(c+1,c+n+1,cmp);	
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}

Submission Info

Judge Result