Cod sursa(job #2301391)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 12 decembrie 2018 21:41:01
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

struct concert
{
    int x, y;
}a[100001];

int d[100001];
int n;

bool cmp(concert a, concert b)
{
    return (a.y<b.y || (a.y==b.y && a.x<b.x));
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; ++i) fin>>a[i].x>>a[i].y;
    sort(a+1, a+n+1, cmp);
    for(int i=1; i<=n; ++i)
    {
        d[i]=d[i-1];
        int st=0, dr=i;
        while(st<dr)
        {
            int m=(st+dr+1)/2;
            if(a[m].y>a[i].x) dr=m-1;
            else st=m;
        }
        d[i]=max(d[i], d[st]+a[i].y-a[i].x);
    }
    fout<<d[n]<<"\n";
    return 0;
}