Cod sursa(job #485155)

Utilizator DraStiKDragos Oprica DraStiK Data 17 septembrie 2010 12:54:31
Problema Stalpi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <algorithm>
#include <set>
using namespace std;

#define mp make_pair
#define DIM 100005
#define sc second
#define fs first

multiset <pair <long long,int> > arb;
pair <pair <int,int>,int> v[DIM];
long long bst[DIM];
int x[DIM];
int n;

void read ()
{
    int i,c,s,d;

    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
    {
        scanf ("%d%d%d%d",&x[i],&c,&s,&d);
        v[i]=mp (mp (x[i]-s,x[i]+d),c);
    }
}

void solve ()
{
    int i,j;

    sort (x+1,x+n+1);
    sort (v+1,v+n+1);

    for (j=0, i=1; i<=n; ++i)
    {
        for ( ; j<=n && x[j]<v[i].fs.fs; ++j)
        {
            for ( ; (*arb.begin ()).sc<x[j]; arb.erase (arb.begin ()));
            bst[j]=(*arb.begin ()).fs;
        }
        if (j)
            arb.insert (mp (bst[j-1]+v[i].sc,v[i].fs.sc));
        else
            arb.insert (mp (v[i].sc,v[i].fs.sc));
    }
    for ( ; j<=n; ++j)
    {
        for ( ; (*arb.begin ()).sc<x[j]; arb.erase (arb.begin ()));
        bst[j]=(*arb.begin ()).fs;
    }
    printf ("%lld",bst[n]);
}

int main ()
{
    freopen ("stalpi.in","r",stdin);
    freopen ("stalpi.out","w",stdout);

    read ();
    solve ();

    return 0;
}