Cod sursa(job #1967075)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 15 aprilie 2017 21:11:12
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 100005;
struct ABC
{
    int st, dr;
};
ABC v[NMAX];
int st[NMAX];
long long int smax[NMAX];
long long int ssmax[NMAX];
bool cmp(ABC first, ABC second)
{
    if(first.st == second.st)
        return first.dr < second.dr;
    return first.st < second.st;
}

int main()
{
    int i, n, top;
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d", &n);
    for(i = 0;i < n; ++i) {
        scanf("%d%d", &v[i].st, &v[i].dr);
    }
    sort(v, v + n, cmp);
    top = 1;
    st[top] = 0;
    smax[0] = v[0].dr - v[0].st;
    ssmax[0] = smax[0];
    for(i = 1;i < n; ++i) {
        while(top > 0 && v[i].st < v[st[top]].dr) {
            --top;
        }
        smax[i] = ssmax[st[top]] + v[i].dr - v[i].st;
        ssmax[i] = max(ssmax[i - 1], smax[i]);
        st[++top] = i;
    }
    printf("%lld\n", ssmax[n - 1]);
    return 0;
}