Cod sursa(job #1627600)

Utilizator Athena99Anghel Anca Athena99 Data 3 martie 2016 17:59:54
Problema Stalpi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#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;
}