Cod sursa(job #290779)

Utilizator raduzerRadu Zernoveanu raduzer Data 28 martie 2009 18:22:48
Problema Stalpi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 100010;
const int INF = 0x3f3f3f3f;

int n;
int a[MAX_N], aib[MAX_N];

struct stalp {
	int c, s, d;
} p[MAX_N];

int cmp(stalp a, stalp b)
{
	return a.s > b.s;
}

int bs(int val)
{
	int st = 1, dr = n + 1, mij;
	
	while (st < dr)
	{
		mij = st + (dr - st) / 2;
		
		if (a[mij] <= val) st = mij + 1;
		else dr = mij;
	}
	
	return st;
}

int bs2(int val)
{
	int st = 1, dr = n, mij;
	
	while (st < dr)
	{
		mij = (st + dr) / 2 ;
		
		if (a[mij] < val) st = mij + 1;
		else dr = mij;
	}
	
	return st;
}

inline void checkMin(int &a, int b)
{
	if (a > b) a = b;
}

inline int lsb(int x) { return x & (x - 1) ^ x; }

void update(int poz, int val)
{
	while (poz <= n + 1)
	{
		checkMin(aib[poz], val);
		poz += lsb(poz);
	}
}

int query(int poz)
{
	int ret = INF;
	
	while (poz)
	{
		checkMin(ret, aib[poz]);
		poz -= lsb(poz);
	}
	
	return ret;
}

int main()
{
	int i, x1, x2, x3, x4;
	freopen("stalpi.in", "r", stdin);
	freopen("stalpi.out", "w", stdout);
	
	scanf("%d", &n);
	for (i = 1; i <= n; ++i) 
	{
		scanf("%d %d %d %d", &x1, &x2, &x3, &x4);
		
		p[i].s = x1 - x3;
		p[i].d = x1 + x4;
		p[i].c = x2;
		a[i] = x1;
	}
	
	memset(aib, INF, sizeof(aib));
	a[n + 1] = INF;
	sort(a + 1, a + n + 1);
	update(n + 1, 0);
	sort(p + 1, p + n + 1, cmp);
	
	for (i = 1; i <= n; ++i) 
	{
		int R = bs(p[i].d);
		int L = bs2(p[i].s);
		
		update(L, query(R) + p[i].c);
	}
	
	printf("%d\n", query(1));
}