Submission #2072418


Source Code Expand

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

signed main(){
	int n,l,a[100000],b[100000],c[100000],d[100000],cnt[100000],mi = INF,add = 0,tmp = 0;
	__int128 ans = 0;
	vector<int> vec,evt[100000];
	cin >> n >> l;
	add = -l;
	int mac = -INF;
	for(int i = 0;i < n;i++){
		cin >> a[i] >> b[i] >> c[i];
		tmp += b[i] - c[i];
		cnt[i] = tmp;
		mac = max(mac,tmp);
	}
	for(int i = 0;i < n;i++){
		cnt[i] -= mac;
		vec.push_back(cnt[i]);
	}
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	for(int i = 0;i < n;i++){
		d[i] = a[i + 1] - a[i];
		if(d[i] < 0) d[i] += l;
		ans += (__int128)(abs(cnt[i]) * d[i]);
		int ind = lower_bound(vec.begin(),vec.end(),cnt[i]) - vec.begin();
		evt[ind].push_back(i);
	}
	for(int i = vec.size() - 1;i >= 0;i--){
		for(int v : evt[i]) add += 2 * d[v];
		if(ans <= INF) mi = min(mi,(int)ans);
		if(i) ans += (__int128)(add * (vec[i] - vec[i - 1]));
	}
	if(ans <= INF) mi = min(mi,(int)ans);
	cout << mi << endl;
	return 0;
}

Submission Info

Submission Time
Task D - タクシー
User hoget157
Language C++14 (GCC 5.4.1)
Score 45
Code Size 1065 Byte
Status WA
Exec Time 112 ms
Memory 10484 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 15 / 15 30 / 30 0 / 55
Status
AC × 2
AC × 22
AC × 42
AC × 47
WA × 15
Set Name Test Cases
Sample subtask0-sample-01.txt, subtask0-sample-02.txt
Subtask1 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt
Subtask2 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt
Subtask3 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt
Case Name Status Exec Time Memory
subtask0-sample-01.txt AC 3 ms 4608 KB
subtask0-sample-02.txt AC 3 ms 5888 KB
subtask1-01.txt AC 3 ms 5376 KB
subtask1-02.txt AC 3 ms 6016 KB
subtask1-03.txt AC 6 ms 5120 KB
subtask1-04.txt AC 6 ms 6400 KB
subtask1-05.txt AC 6 ms 6656 KB
subtask1-06.txt AC 6 ms 5248 KB
subtask1-07.txt AC 6 ms 5120 KB
subtask1-08.txt AC 6 ms 6528 KB
subtask1-09.txt AC 6 ms 6016 KB
subtask1-10.txt AC 7 ms 6272 KB
subtask1-11.txt AC 6 ms 5376 KB
subtask1-12.txt AC 6 ms 6400 KB
subtask1-13.txt AC 6 ms 6272 KB
subtask1-14.txt AC 6 ms 5120 KB
subtask1-15.txt AC 6 ms 6144 KB
subtask1-16.txt AC 6 ms 6400 KB
subtask1-17.txt AC 6 ms 5248 KB
subtask1-18.txt AC 6 ms 6656 KB
subtask1-19.txt AC 7 ms 6400 KB
subtask1-20.txt AC 6 ms 5888 KB
subtask2-01.txt AC 8 ms 6528 KB
subtask2-02.txt AC 8 ms 6272 KB
subtask2-03.txt AC 6 ms 5632 KB
subtask2-04.txt AC 7 ms 5248 KB
subtask2-05.txt AC 6 ms 5376 KB
subtask2-06.txt AC 6 ms 5760 KB
subtask2-07.txt AC 8 ms 5632 KB
subtask2-08.txt AC 8 ms 6656 KB
subtask2-09.txt AC 8 ms 4864 KB
subtask2-10.txt AC 7 ms 6656 KB
subtask2-11.txt AC 8 ms 5376 KB
subtask2-12.txt AC 8 ms 6016 KB
subtask2-13.txt AC 8 ms 6272 KB
subtask2-14.txt AC 7 ms 6656 KB
subtask2-15.txt AC 8 ms 5888 KB
subtask2-16.txt AC 8 ms 6272 KB
subtask2-17.txt AC 8 ms 5888 KB
subtask2-18.txt AC 6 ms 5248 KB
subtask2-19.txt AC 8 ms 6528 KB
subtask2-20.txt AC 7 ms 4864 KB
subtask3-01.txt AC 24 ms 7036 KB
subtask3-02.txt AC 56 ms 8056 KB
subtask3-03.txt WA 109 ms 10356 KB
subtask3-04.txt AC 88 ms 8820 KB
subtask3-05.txt WA 112 ms 10356 KB
subtask3-06.txt WA 110 ms 10356 KB
subtask3-07.txt WA 109 ms 10356 KB
subtask3-08.txt WA 109 ms 10356 KB
subtask3-09.txt WA 75 ms 8436 KB
subtask3-10.txt WA 109 ms 10356 KB
subtask3-11.txt AC 70 ms 8564 KB
subtask3-12.txt WA 108 ms 10356 KB
subtask3-13.txt WA 107 ms 10356 KB
subtask3-14.txt WA 110 ms 10356 KB
subtask3-15.txt WA 109 ms 10356 KB
subtask3-16.txt WA 109 ms 10484 KB
subtask3-17.txt WA 109 ms 10356 KB
subtask3-18.txt AC 101 ms 9972 KB
subtask3-19.txt WA 106 ms 10356 KB
subtask3-20.txt WA 108 ms 10356 KB