Pagini recente » Cod sursa (job #2363586) | Cod sursa (job #1032264) | Cod sursa (job #2824466) | Cod sursa (job #1623640) | Cod sursa (job #479839)
Cod sursa(job #479839)
#include <algorithm>
#include <stdio.h>
#include <set>
#define MAX 100010
#define ll long long
#define mp make_pair
#define f first
#define s second
using namespace std;
int n, rx;
int x[MAX];
ll sol[MAX];
multiset <pair <ll, int> > setEl;
pair <pair <int, int>, int> vctInt[MAX];
int main()
{
freopen("stalpi.in", "r", stdin);
freopen("stalpi.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int c, s, d;
scanf("%d %d %d %d", &x[i], &c, &s, &d);
vctInt[i] = mp(mp(x[i] - s, x[i] + d), c);
}
sort(x + 1, x + 1 + n);
sort(vctInt + 1, vctInt + 1 + n);
for (int i = 1; i <= n; i++)
{
for (; rx <= n && x[rx] < vctInt[i].f.f; rx++)
{
for (; (*setEl.begin()).s < x[rx]; setEl.erase(setEl.begin()));
sol[rx] = (*setEl.begin()).f;
}
setEl.insert(mp(sol[rx - 1] + vctInt[i].s, vctInt[i].f.s));
}
for (; rx <= n; rx++)
{
for (; (*setEl.begin()).s < x[rx]; setEl.erase(setEl.begin()));
sol[rx] = (*setEl.begin()).f;
}
printf("%lld\n", sol[n]);
fclose(stdin);
fclose(stdout);
return 0;
}