Cod sursa(job #1104933)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 11 februarie 2014 11:25:40
Problema Stalpi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>
#include <set>
#include <algorithm>
#define nmax 100005
using namespace std;

struct stalp {
    int x,nr;
};

long long v[nmax];
stalp r[nmax],l[nmax],s[nmax];
int c[nmax];
long long valoare[nmax];
multiset <long long> heap;
int n;

bool cmp(stalp a,stalp b) {
    return a.x < b.x;
}

int main() {
    freopen("stalpi.in","r",stdin);
    freopen("stalpi.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        int left,right;
        scanf("%d %d %d %d",&s[i].x,&c[i],&left,&right);
        l[i].x = s[i].x - left;
        r[i].x = s[i].x + right;
        s[i].nr = l[i].nr = r[i].nr = i;
    }
    sort(r+1,r+n+1,cmp);
    sort(l+1,l+n+1,cmp);
    sort(s+1,s+n+1,cmp);
    int j=1,k=1;
    for (int i=1;i<=n;i++) {
        while (l[j].x <= s[i].x && j <= n) {
            heap.insert(c[l[j].nr]+v[i-1]);
            valoare[l[j].nr] = c[l[j].nr]+v[i-1];
            j++;
        }
        while (r[k].x < s[i].x && k <= n) {
            heap.erase(heap.find(valoare[r[k].nr]));
            k++;
        }
        v[i] = *heap.begin();
    }
    printf("%lld\n",v[n]);
    return 0;
}