Cod sursa(job #1669723)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 30 martie 2016 23:02:23
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<vector>
#define NMax 100005
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int N,Sol,DP[NMax];

vector < pair<int,int> > V;

bool Cmp(pair<int,int> A,pair<int,int> B)
{
    if(A.second > B.second) return 0;
    if(A.second == B.second)
        return (A.first < B.first);
    return 1;
}

void Read()
{
    fin>>N;

    for(int i=1;i<=N;++i)
    {
        int x,y;    fin>>x>>y;
        V.push_back(make_pair(x,y));
    }

    sort(V.begin(),V.end(),Cmp);
}

void Solve()
{
    DP[1] = V[1].second - V[1].first;

    for(int i=2;i<=N;++i)
    {
        int j=i-1,st,dr,mid;

        st = 1;
        dr = i-1;
        mid = (st + dr) / 2;

        while(st<=dr)
        {
            if(V[mid].second <= V[i].first){    j = mid;    st = mid+1; }
            else    dr = mid-1;
            mid = (st+dr)/2;
        }

        DP[i] = max(DP[i-1],DP[j]+V[i].second-V[i].first);
    }

    Sol = DP[N];
}

void Print()
{
    fout<<Sol<<"\n";
}

int main()
{
    Read();
    Solve();
    Print();

    fin.close();
    fout.close();
    return 0;
}