Submission #5403

#	Time	Username	Problem	Language	Result	Execution time	Memory
5403		Qwaz	Divide and conquer (IZhO14_divide)	C++98	100 / 100	96 ms	7336 KiB

divide

#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;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52