Cod sursa(job #2072368)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 21 noiembrie 2017 19:38:49
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<fstream>
#include<algorithm>

using namespace std;

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

const int NMax=100000;
int N;
pair < int, int > DP[NMax+5],Vect[NMax+5];

int BinarySearch(int i)
{
    int Left=1,Right=i-1,Mid,Sol;
    while(Left<=Right)
    {
        Mid=(Left+Right)/2;
        if(DP[Mid].first<=Vect[i].second)
        {
            Sol=Mid;
            Left=Mid+1;
        }
        else
            Right=Mid-1;
    }
    return Sol;
}

int main()
{
    fin>>N;
    for(int i=1; i<=N; i++)
        fin>>Vect[i].second>>Vect[i].first;
    sort(Vect+1,Vect+1+N);
    DP[1].first=Vect[1].first;
    DP[1].second=Vect[1].first-Vect[1].second;
    for(int i=2; i<=N; i++)
    {
        if(Vect[i].second<DP[1].first && (Vect[i].first-Vect[i].second)>DP[i-1].second)
        {
            DP[i].first=Vect[i].first;
            DP[i].second=Vect[i].first-Vect[i].second;
            continue;
        }
        else
            if(Vect[i].second<DP[1].first && (Vect[i].first-Vect[i].second)<=DP[i-1].second)
            {
                DP[i]=DP[i-1];
                continue;
            }
        {
            int Sol=BinarySearch(i);
            if(Vect[i].first-Vect[i].second+DP[Sol].second>DP[i-1].second)
            {
                DP[i].first=Vect[i].first;
                DP[i].second=Vect[i].first-Vect[i].second+DP[Sol].second;
            }
            else
                DP[i]=DP[i-1];
        }

    }
    fout<<DP[N].second<<'\n';
}