Cod sursa(job #1669730)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 30 martie 2016 23:07:27
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 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)
{
    return (A.second < B.second);
}

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()
{
    for(int i=1;i<=N;++i)
    {
        int j = 0,st,dr,mid;

        st = 1;
        dr = i-1;

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

        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;
}