Cod sursa(job #1783188)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 18 octombrie 2016 20:43:37
Problema Heavy metal Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <cstdio>
#include <algorithm>
#define VAL 100005

using namespace std;

struct interval
{
    int l;
    int r;
};

interval v[VAL];

int N, i, mx;
int best[VAL];

bool cmp(interval a, interval b)
{
    return a.r<b.r;
}

int cautbin()
{
    int be=1;
    int en=i;
    int ans=0;
    int mid;
    while (be<=en)
    {
        mid=(be+en) / 2;
        if (v[mid].r<v[i].l)
        {
            ans=mid;
            be=mid+1;
        }
        else
          en=mid-1;
    }
    return ans;
}

int main()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);
    scanf("%d", &N);
    for (i=1; i<=N; i++)
      scanf("%d %d", &v[i].l, &v[i].r);
    sort(v+1, v+N+1, cmp);
    for (i=1; i<=N; i++)
    {
        v[i].r--;
        best[i]=best[cautbin()]+v[i].r-v[i].l+1;
        mx=max(mx, best[i]);
    }
    printf("%d\n", mx);
    return 0;
}