Pagini recente » Cod sursa (job #2232446) | Cod sursa (job #757213) | Cod sursa (job #1405842) | Cod sursa (job #2326301) | Cod sursa (job #1104933)
#include <cstdio>
#include <set>
#include <algorithm>
#define nmax 100005
using namespace std;
struct stalp {
int x,nr;
};
long long v[nmax];
stalp r[nmax],l[nmax],s[nmax];
int c[nmax];
long long valoare[nmax];
multiset <long long> heap;
int n;
bool cmp(stalp a,stalp b) {
return a.x < b.x;
}
int main() {
freopen("stalpi.in","r",stdin);
freopen("stalpi.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) {
int left,right;
scanf("%d %d %d %d",&s[i].x,&c[i],&left,&right);
l[i].x = s[i].x - left;
r[i].x = s[i].x + right;
s[i].nr = l[i].nr = r[i].nr = i;
}
sort(r+1,r+n+1,cmp);
sort(l+1,l+n+1,cmp);
sort(s+1,s+n+1,cmp);
int j=1,k=1;
for (int i=1;i<=n;i++) {
while (l[j].x <= s[i].x && j <= n) {
heap.insert(c[l[j].nr]+v[i-1]);
valoare[l[j].nr] = c[l[j].nr]+v[i-1];
j++;
}
while (r[k].x < s[i].x && k <= n) {
heap.erase(heap.find(valoare[r[k].nr]));
k++;
}
v[i] = *heap.begin();
}
printf("%lld\n",v[n]);
return 0;
}