Pagini recente » Statistici Traian SF (traiansf) | Profil synnks | Monitorul de evaluare | Cod sursa (job #163079) | Cod sursa (job #2072368)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMax=100000;
int N;
pair < int, int > DP[NMax+5],Vect[NMax+5];
int BinarySearch(int i)
{
int Left=1,Right=i-1,Mid,Sol;
while(Left<=Right)
{
Mid=(Left+Right)/2;
if(DP[Mid].first<=Vect[i].second)
{
Sol=Mid;
Left=Mid+1;
}
else
Right=Mid-1;
}
return Sol;
}
int main()
{
fin>>N;
for(int i=1; i<=N; i++)
fin>>Vect[i].second>>Vect[i].first;
sort(Vect+1,Vect+1+N);
DP[1].first=Vect[1].first;
DP[1].second=Vect[1].first-Vect[1].second;
for(int i=2; i<=N; i++)
{
if(Vect[i].second<DP[1].first && (Vect[i].first-Vect[i].second)>DP[i-1].second)
{
DP[i].first=Vect[i].first;
DP[i].second=Vect[i].first-Vect[i].second;
continue;
}
else
if(Vect[i].second<DP[1].first && (Vect[i].first-Vect[i].second)<=DP[i-1].second)
{
DP[i]=DP[i-1];
continue;
}
{
int Sol=BinarySearch(i);
if(Vect[i].first-Vect[i].second+DP[Sol].second>DP[i-1].second)
{
DP[i].first=Vect[i].first;
DP[i].second=Vect[i].first-Vect[i].second+DP[Sol].second;
}
else
DP[i]=DP[i-1];
}
}
fout<<DP[N].second<<'\n';
}