Cod sursa(job #137196)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 17 februarie 2008 09:59:04
Problema Stalpi Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasele 11-12 Marime 1.1 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const long MAX=100010; //TODO de modificat la loc
//const long MAX = 10;
struct stalp { 
	long x,c,st,dr;
} S[MAX];
int comp(const stalp &A, const stalp &B) { return A.x<B.x; }

long n, sum;
long Cost[MAX], T[MAX];
bool ok[MAX];

void solve1() {
	sort(S, S+n, comp);
	memset(Cost, 0x3f, sizeof(long)*(n+2));
	for (long i=0; i<n; ++i) {
		if ( Cost[i]>S[i].c )
			Cost[i] = S[i].c, T[i] = i;

		long delta = S[i].x-S[i].st;
		for (long j=i-1; j>=0 && S[j].x>=delta; --j)
			if ( Cost[j]>S[i].c )
				Cost[j]=S[i].c, T[j] = i;
		delta = S[i].x+S[i].dr;
		for (long j=i+1; j<n && S[j].x<=delta; ++j)
			if ( Cost[j]>S[i].c )
				Cost[j]=S[i].c, T[j] = i;
	}
	sum = 0;
	for (long i=0; i<n; ++i)
		if ( !ok[T[i]] ) 
			sum += S[T[i]].c, ok[T[i]] = 1;
	return ;
	for (long i=0; i<n; ++i)
		printf("%ld\n", T[i]);
}

int main() {
	freopen("stalpi.in", "r", stdin);
	scanf("%ld", &n);
	for (long i=0; i<n; ++i)
		scanf("%ld %ld %ld %ld", &S[i].x, &S[i].c, &S[i].st, &S[i].dr);
	fclose(stdin);

	solve1();
	
	fprintf(fopen("stalpi.out","w"), "%ld\n", sum);
	return 0;
}