Cod sursa(job #1799849)

Utilizator LizaSzabo Liza Liza Data 6 noiembrie 2016 21:36:43
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const  int NMax=100000;
int  DP[NMax],n;

struct str
{
    int a, b;
};
bool cmp (str x, str y)
{
    return x.b  < y.b;
}


str d[NMax];
void read()
{
    fin>>n;
    for (int i=1;i<=n;++i){
        fin>>d[i].a>>d[i].b;

    }
}






void sol()
{
    sort(d+1,d+n+1,cmp);
    for(int i=1;i<=n;++i)
        {
            int j=i;
        while(d[j].b>d[i].a)
        {
         j--;
        }
    DP[i]=max(DP[i-1],DP[j]+(d[i].b-d[i].a));

    }
}



int main()
{
read();
sol();
fout<<DP[n]<<'\n';
    return 0;
}