Cod sursa(job #851846)

Utilizator stoicatheoFlirk Navok stoicatheo Data 10 ianuarie 2013 15:36:11
Problema Stalpi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
# 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]);
}