Cod sursa(job #1692081)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 20 aprilie 2016 01:31:49
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

struct ITV{
    int a,b,ans;
    inline bool operator < (ITV arg) const {
        return a<arg.a;
    }
    inline bool operator < (int arg) const {
        return a<arg;
    }
};

vector<ITV> v;

int main(void){
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n,ans=0;
    ITV tmp;
    scanf("%d",&n);

    while(n--){
        scanf("%d%d",&tmp.a,&tmp.b);
        tmp.ans=tmp.b-tmp.a;
        v.push_back(tmp);
    }
    sort(v.begin(), v.end());

    for(int i=0; i<v.size(); ++i){
        auto it = lower_bound(v.begin(), v.end(), v[i].b);
        if(it!=v.end())
            it->ans=max(it->ans, (it->b)-(it->a)+v[i].ans);
    }
    for(int i=0; i<v.size(); ++i)
        ans=max(ans,v[i].ans);
    printf("%d",ans);
    return 0;
}