Pagini recente » Cod sursa (job #335256) | Cod sursa (job #188187) | Cod sursa (job #2724608) | Cod sursa (job #570278) | Cod sursa (job #485155)
Cod sursa(job #485155)
#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;
}