Pagini recente » Cod sursa (job #1364161) | Cod sursa (job #1799849)
#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;
}