Cod sursa(job #137291)

Utilizator maria_pparcalabescu maria daniela maria_p Data 17 februarie 2008 11:01:36
Problema Stalpi Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasa a 10-a Marime 0.93 kb
#include<cstdio>
#include<algorithm>
struct stalp{
	long x;
	long c;
	long st,dr;
}a[100010];
long n,i,cost[100010],t[100010],j,ok,cmax,rez;
bool ad[100010];
bool cmp(stalp x,stalp y){
	return (x.x<y.x);
}
int main(){
	freopen("stalpi.in","r",stdin);
	freopen("stalpi.out","w",stdout);
	scanf("%ld",&n);cmax=0;
	for(i=0;i<n;i++){
		scanf("%ld%ld%ld%ld",&a[i].x,&a[i].c,&a[i].st,&a[i].dr);
		if(a[i].c>cmax)cmax=a[i].c;
	}
	std::sort(a,a+n,cmp);
	for(i=0;i<n;i++)
		cost[i]=cmax+100;
	for(i=0;i<n;i++) {
		if(a[i].c<cost[i]){
			cost[i] = a[i].c, t[i] = i;
		}
			for(j=i-1;(a[j].x>=a[i].x-a[i].st)&&(j>=0);j--)
				if(a[i].c<cost[j])
					cost[j]=a[i].c,t[j]=i;
			for(j=i+1;(a[j].x<=a[i].x+a[i].dr)&&(j<n);j++)
				if(a[i].c<cost[j])
					cost[j]=a[i].c,t[j]=i;
	}
	rez=0;
	for(i=0;i<n;i++){
		if(ad[t[i]]==0)
			rez+=a[t[i]].c, ad[t[i]]=1;
//		printf("%ld %ld\n",cost[i],t[i]);
	}
	printf("%ld\n",rez);
	fclose(stdin);
	fclose(stdout);
	return 0;
}