제출 #5403

#제출 시각아이디문제언어결과실행 시간메모리
5403Qwaz금 캐기 (IZhO14_divide)C++98
100 / 100
96 ms7336 KiB
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;
const int MAX = 100020;
const ll INF = 1234567890LL;

struct segment {
	int pos;
	ll gSum, eSum;
	bool left;

	bool operator < (const segment &t) const {
		if(eSum-pos == t.eSum-t.pos)
			return left > t.left;
		return eSum-pos < t.eSum-t.pos;
	}
};

int n, dFull;
segment data[MAX<<1];

void input(){
	scanf("%d", &n);

	ll eSum = 0, gSum = 0;

	int i;
	for(i = 0; i<n; i++){
		segment t;
		scanf("%d", &t.pos);

		ll nowG, nowE;
		scanf("%lld%lld", &nowG, &nowE);

		t.left = 1;
		t.gSum = gSum;
		t.eSum = eSum;
		data[dFull++] = t;

		gSum += nowG;
		eSum += nowE;

		t.left = 0;
		t.gSum = gSum;
		t.eSum = eSum;
		data[dFull++] = t;
	}

	sort(data, data+dFull);
}

void solve(){
	int i;
	ll minG = INF * MAX, res = 0;
	for(i = 0; i<dFull; i++){
		if(data[i].left) minG = min(minG, data[i].gSum);
		else res = max(res, data[i].gSum-minG);
	}

	printf("%lld\n", res);
}

int main(){
	input();

	solve();

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...