Cod sursa(job #2048388)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 25 octombrie 2017 23:15:36
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
#define pii pair<int, int>
#define x first
#define y second
const int Nmax = 100000 + 5;
long long n, maxim, dp[Nmax];
pii p[Nmax];
bool cmp(pii a, pii b)
{
    if(a.y == b.y)return a.x < b.x;
    return a.y < b.y;
}
int main()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> p[i].x >> p[i].y;
    sort(p +1 , p + n + 1, cmp);
    dp[1] = p[1].y - p[1].x;
    for(int i = 2, st, dr; i <= n; ++i)
    {
        st = 0; dr = i;
        while(dr - st > 1)
        {
            int mid = st + (dr - st) /2;

            if(p[mid].y <= p[i].x)st = mid;
            else dr = mid;
        }
        if(st == 0)dp[i] = p[i].y - p[i].x;
        else dp[i] = dp[st] + p[i].y - p[i].x;
        if(dp[i] > maxim)maxim = dp[i];
    }
    fout << maxim;
    return 0;
}