Cod sursa(job #479839)

Utilizator MirceaTanaseMircea Tanase MirceaTanase Data 25 august 2010 14:08:03
Problema Stalpi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <algorithm>
#include <stdio.h>
#include <set>

#define MAX 100010
#define ll long long
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, rx;
int x[MAX];
ll sol[MAX];
multiset <pair <ll, int> > setEl;
pair <pair <int, int>, int> vctInt[MAX];

int main()
{
	freopen("stalpi.in", "r", stdin);
	freopen("stalpi.out", "w", stdout);
	
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		int c, s, d;
		scanf("%d %d %d %d", &x[i], &c, &s, &d);

		vctInt[i] = mp(mp(x[i] - s, x[i] + d), c);
	}

	sort(x + 1, x + 1 + n);
	sort(vctInt + 1, vctInt + 1 + n);

	for (int i = 1; i <= n; i++)
	{
		for (; rx <= n && x[rx] < vctInt[i].f.f; rx++)
		{
			for (; (*setEl.begin()).s < x[rx]; setEl.erase(setEl.begin()));

			sol[rx] = (*setEl.begin()).f;
		}

		setEl.insert(mp(sol[rx - 1] + vctInt[i].s, vctInt[i].f.s));
	}
	
	for (; rx <= n; rx++)
	{
		for (; (*setEl.begin()).s < x[rx]; setEl.erase(setEl.begin()));

		sol[rx] = (*setEl.begin()).f;
	}

	printf("%lld\n", sol[n]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}