Pagini recente » Cod sursa (job #2255538) | Cod sursa (job #358787) | Cod sursa (job #2088606) | Cod sursa (job #2157185) | Cod sursa (job #1667953)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,max0,i,j,max1;
struct trup{
int s;
int e;
int d;
}trupe[100005];
bool comp(trup i,trup j)
{
return i.s<j.s || (i.s==j.s && i.e<j.e);
}
int main()
{ int i;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>trupe[i].s;
fin>>trupe[i].e;
trupe[i].d=0;
}
sort(trupe,trupe+n+1,comp);
trupe[1].d=trupe[1].e-trupe[1].s;
max0=trupe[1].d;
for(i=2;i<=n;i++){
max1=0;
for(j=i;j>=1;j--)
if (trupe[i].s>=trupe[j].e && trupe[j].d>max1)
{
max1=trupe[j].d;
break;}
trupe[i].d=(trupe[i].e-trupe[i].s)+max1;
if(trupe[i].d>max0)max0=trupe[i].d;
}
fout<<max0;
fin.close();
fout.close();
return 0;
}