Submission #2195510

---

Source Code Expand

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

long long n,L,a[100009],b[100009],c[100009],minx=(1LL<<60);

long long solve(vector<long long>A,vector<long long>B,vector<long long>C){
	long long cx=0,cost=0;
	for(int i=0;i<B.size();i++){
		for(int j=cx;j<C.size();j++){
			if(C[cx]>=B[i]){
				C[cx]-=B[i];cost+=llabs(A[i]-A[cx])*B[i];
				B[i]=0;break;
			}
			else{
				B[i]-=C[cx];cost+=llabs(A[i]-A[cx])*C[cx];
				C[cx]=0;cx++;
			}
		}
	}
	return cost;
}

int main(){
	cin>>n>>L;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	for(int i=0;i<n;i++){
		vector<long long>A,B,C;
		for(int j=i;j<n+i;j++){
			A.push_back((a[j%n]-a[i]+L)%L);
			B.push_back(b[j%n]);
			C.push_back(c[j%n]);
		}
		minx=min(minx,solve(A,B,C));
	}
	cout<<minx<<endl;
	return 0;
}

Submission Info

Judge Result