Pagini recente » Cod sursa (job #1617832) | Cod sursa (job #2801190) | Cod sursa (job #715863) | Cod sursa (job #1185595) | Cod sursa (job #1013425)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct Participant{
int A;
int B;
} Array[100005];
int N,DP[100005];
bool compare(Participant a,Participant b)
{
return a.B<b.B;
}
void Read()
{
int i;
f>>N;
for(i=1;i<=N;i++)
f>>Array[i].A>>Array[i].B;
sort(Array+1,Array+N+1,compare);
}
int Binary_Search(int val,int poz)
{
int st=1,dr=poz,mid,sol=0;
while(st<=dr)
{
mid=(st+dr)/2;
if(Array[mid].B<=val)
sol=mid,st=mid+1;
else
dr=mid-1;
}
return sol;
}
void Browse()
{
int i;
DP[1]=Array[1].B-Array[1].A;
for(i=2;i<=N;i++)
DP[i]=max(DP[i-1],DP[Binary_Search(Array[i].A,i-1)]+Array[i].B-Array[i].A);
g<<DP[N]<<"\n";
}
int main()
{
Read();
Browse();
return 0;
}