Pagini recente » Cod sursa (job #2677044) | Cod sursa (job #1483302) | Cod sursa (job #2208239) | Cod sursa (job #2167844) | Cod sursa (job #851846)
Cod sursa(job #851846)
# include <algorithm>
# include <cstdio>
# include <set>
using namespace std;
# define x first
# define y second
# define EL (*ST.begin ())
typedef long long ll;
const char *FIN = "stalpi.in", *FOU = "stalpi.out";
const int MAX = 100005;
multiset < pair <ll, int> > ST;
pair < pair <int, int>, int > V[MAX];
ll dp[MAX];
int N, X[MAX];
int main (void) {
freopen (FIN, "r", stdin);
scanf ("%d", &N);
for (int i = 1, C, S, D; i <= N; ++i) {
scanf ("%d %d %d %d", X + i, &C, &S, &D);
V[i] = make_pair (make_pair (X[i] - S, X[i] + D), C);
}
sort (X + 1, X + N + 1);
sort (V + 1, V + N + 1);
int i, j;
for (i = 1, j = 0; i <= N; ++i) {
for (; j <= N && X[j] < V[i].x.x; ++j) {
for (; EL.y < X[j]; ST.erase (EL));
dp[j] = EL.x;
}
ST.insert (make_pair (V[i].y + (j ? dp[j - 1] : 0), V[i].x.y));
}
for (; j <= N; ++j) {
for (; EL.y < X[j]; ST.erase (EL));
dp[j] = EL.x;
}
fprintf (fopen (FOU, "w"), "%lld", dp[N]);
}