Submission #2072483

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define INF 1e+18
using namespace std;

typedef pair<int,int> P;

signed main(){
	int n,l,a[100010] = {},b[100000],c[100000],d[100000],cnt[100000],tmp = 0;
	vector<P> vec;
	cin >> n >> l;
	for(int i = 0;i < n;i++){
		cin >> a[i] >> b[i] >> c[i];
		tmp += b[i] - c[i];
		cnt[i] = tmp;
	}
	for(int i = 0;i < n;i++){
		d[i] = a[i + 1] - a[i];
		if(d[i] < 0) d[i] += l;
		vec.push_back(P(cnt[i],d[i]));
	}
	sort(vec.begin(),vec.end());
	int sum = 0;
	for(int i = 0;i < n;i++){
		sum += vec[i].second;
		if(sum * 2 >= l){
			int ans = 0;
			for(int j = 0;j < n;j++) ans += abs(vec[i].first - cnt[j]) * d[j];
			cout << ans << endl;
			break;
		}
	}
	return 0;
}

Submission Info

Judge Result