Pagini recente » Cod sursa (job #1405374) | Cod sursa (job #1469456) | Cod sursa (job #1208921) | Cod sursa (job #119110) | Cod sursa (job #137289)
Cod sursa(job #137289)
#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+1;
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;
}