Pagini recente » Cod sursa (job #1620247) | Cod sursa (job #1837536) | Cod sursa (job #1532767) | Cod sursa (job #2696475) | Cod sursa (job #2764898)
#include <fstream>
#include <algorithm>
using namespace std;
struct formatie{int st,dr;};
ifstream fi("heavymetal.in");
ofstream fo("heavymetal.out");
int n;
formatie F[100001];
int OPT[100001];
int cmp(formatie a, formatie b)
{
if (a.dr<b.dr)
return 1;
return 0;
}
int main()
{
fi>>n;
for (int i=1;i<=n;i++)
fi>>F[i].st>>F[i].dr;
sort(F+1,F+n+1,cmp);
F[0].st=F[0].dr=-1;
OPT[0]=0;
for (int i=1;i<=n;i++)
{
/// se calculeaza OPT[i]
OPT[i]=OPT[i-1];
/// se cauta binar P[i]
int le,ri;
le=0;
ri=i-1;
while (le!=ri)
{
int m;
m=(le+ri+1)/2;
if (F[i].st>=F[m].dr)
le=m;
else
ri=m-1;
}
if (F[i].dr-F[i].st+OPT[le]>OPT[i])
OPT[i]=F[i].dr-F[i].st+OPT[le];
}
fo<<OPT[n];
fi.close();
fo.close();
return 0;
}