Submission #1047180


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
typedef long long ll;
typedef vector<ll> vec;

const int MAX_N=1e5;

int N,L;
ll A[MAX_N],B[MAX_N],C[MAX_N];

vec xs;

void compress(){
	sort(xs.begin(),xs.end());
	xs.erase(unique(xs.begin(),xs.end()),xs.end());
}

ll f(ll x){
	ll res=abs(x)*(L-A[N-1]);
	REP(i,N-1){
		res+=abs(C[i]-(B[i]+x))*(A[i+1]-A[i]);
	}
	return res;
}

int main(){
	scanf("%d %d",&N,&L);
	REP(i,N){
		scanf("%lld %lld %lld",&A[i],&B[i],&C[i]);
	}
	FOR(i,1,N){
		B[i]+=B[i-1];
		C[i]+=C[i-1];
	}
	REP(i,N-1){
		xs.push_back(C[i]-B[i]);
	}
	compress();
	int l=0,r=xs.size();
	while(r-l>2){
		int a=(2*l+r)/3,b=(l+2*r)/3;
		if (f(xs[a])<f(xs[b])){
			r=b;
		}else{
			l=a;
		}
	}
	printf("%lld\n",min(f(xs[l]),f(xs[r-1])));
	return 0;
}

Submission Info

Submission Time
Task D - タクシー
User addeight
Language C++ (G++ 4.6.4)
Score 45
Code Size 879 Byte
Status WA
Exec Time 64 ms
Memory 4292 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:29:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:31:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

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 × 61
WA × 1
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 20 ms 916 KB
subtask0-sample-02.txt AC 16 ms 924 KB
subtask1-01.txt AC 16 ms 792 KB
subtask1-02.txt AC 17 ms 924 KB
subtask1-03.txt AC 20 ms 1056 KB
subtask1-04.txt AC 19 ms 1056 KB
subtask1-05.txt AC 20 ms 1056 KB
subtask1-06.txt AC 19 ms 928 KB
subtask1-07.txt AC 20 ms 972 KB
subtask1-08.txt AC 20 ms 1052 KB
subtask1-09.txt AC 20 ms 1052 KB
subtask1-10.txt AC 18 ms 1056 KB
subtask1-11.txt AC 20 ms 928 KB
subtask1-12.txt AC 20 ms 1048 KB
subtask1-13.txt AC 20 ms 924 KB
subtask1-14.txt AC 20 ms 1056 KB
subtask1-15.txt AC 19 ms 1056 KB
subtask1-16.txt AC 20 ms 928 KB
subtask1-17.txt AC 20 ms 1052 KB
subtask1-18.txt AC 19 ms 1056 KB
subtask1-19.txt AC 20 ms 1056 KB
subtask1-20.txt AC 18 ms 928 KB
subtask2-01.txt AC 20 ms 1052 KB
subtask2-02.txt AC 20 ms 1048 KB
subtask2-03.txt AC 20 ms 1056 KB
subtask2-04.txt AC 20 ms 928 KB
subtask2-05.txt AC 20 ms 1056 KB
subtask2-06.txt AC 19 ms 1056 KB
subtask2-07.txt AC 20 ms 928 KB
subtask2-08.txt AC 19 ms 992 KB
subtask2-09.txt AC 20 ms 1056 KB
subtask2-10.txt AC 19 ms 1056 KB
subtask2-11.txt AC 20 ms 1052 KB
subtask2-12.txt AC 18 ms 1052 KB
subtask2-13.txt AC 19 ms 1052 KB
subtask2-14.txt AC 20 ms 1052 KB
subtask2-15.txt AC 20 ms 1056 KB
subtask2-16.txt AC 20 ms 928 KB
subtask2-17.txt AC 20 ms 1052 KB
subtask2-18.txt AC 19 ms 928 KB
subtask2-19.txt AC 20 ms 920 KB
subtask2-20.txt AC 20 ms 928 KB
subtask3-01.txt AC 27 ms 1692 KB
subtask3-02.txt AC 41 ms 2588 KB
subtask3-03.txt AC 62 ms 4248 KB
subtask3-04.txt AC 61 ms 4240 KB
subtask3-05.txt AC 64 ms 4292 KB
subtask3-06.txt AC 63 ms 4248 KB
subtask3-07.txt AC 63 ms 4180 KB
subtask3-08.txt AC 62 ms 4252 KB
subtask3-09.txt AC 53 ms 4248 KB
subtask3-10.txt WA 63 ms 4244 KB
subtask3-11.txt AC 48 ms 4248 KB
subtask3-12.txt AC 63 ms 4252 KB
subtask3-13.txt AC 62 ms 4196 KB
subtask3-14.txt AC 63 ms 4248 KB
subtask3-15.txt AC 62 ms 4200 KB
subtask3-16.txt AC 63 ms 4240 KB
subtask3-17.txt AC 63 ms 4256 KB
subtask3-18.txt AC 62 ms 4192 KB
subtask3-19.txt AC 62 ms 4244 KB
subtask3-20.txt AC 63 ms 4248 KB