Cod sursa(job #1692220)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 20 aprilie 2016 14:54:19
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int NMAX = 100005;

vector<PII> v;
int d[NMAX];

bool cmp(PII a, PII b){
    return a.second<b.second;
}

int main(void) {
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int n,a,b,m_ans=0;
    scanf("%d",&n);
    for(int i=0; i<n; ++i){
        scanf("%d%d",&a,&b);
        v.push_back(make_pair(a,b));
    }
    sort(v.begin(), v.end(), cmp);

    for(int j,i=0; i<n; ++i){
        if(i){
            auto it = --upper_bound(v.begin(), v.end(), make_pair(v[i].first, v[i].first), cmp);
            j=it-v.begin();
        }
        else
            j=-1;

        if(j>=0)
            d[i]=max(v[i].second-v[i].first+d[j], m_ans);
        else
            d[i]=max(v[i].second-v[i].first, m_ans);

        m_ans=max(d[i],m_ans);
    }
    printf("%d",m_ans);
    return 0;
}