Pagini recente » Cod sursa (job #2507192) | Cod sursa (job #1169254) | Cod sursa (job #936458) | Cod sursa (job #49837) | Cod sursa (job #1627600)
#include <algorithm>
#include <fstream>
#include <set>
using namespace std;
ifstream fin("stalpi.in");
ofstream fout("stalpi.out");
const int nmax= 100000;
struct str {
int x, y;
} l[nmax+1], r[nmax+1], x[nmax+1];
int c[nmax+1], d[nmax+1], aux[nmax+1];
bool comp( str x, str y ) {
return x.x<y.x;
}
multiset <int> s;
int main( ) {
int n;
fin>>n;
for ( int i= 1; i<=n; ++i ) {
int a, b;
fin>>x[i].x>>c[i]>>a>>b;
l[i].x= x[i].x-a, r[i].x= x[i].x+b;
l[i].y= r[i].y= x[i].y= i;
}
sort( x+1, x+n+1, comp ) ;
sort( l+1, l+n+1, comp ) ;
sort( r+1, r+n+1, comp ) ;
for ( int i= 1, j1= 1, j2= 1; i<=n; ++i ) {
for ( ; j1<=n && x[i].x>=l[j1].x; ++j1 ) {
aux[l[j1].y]= c[l[j1].y]+d[i-1];
s.insert(aux[l[j1].y]);
}
for ( ; j2<=n && x[i].x>r[j2].x; ++j2 ) {
s.erase(s.find(aux[r[j2].y]));
}
multiset <int>::iterator it= s.begin();
d[i]= *it;
}
fout<<d[n]<<"\n";
return 0;
}