Pagini recente » Cod sursa (job #712715) | Cod sursa (job #107289) | Cod sursa (job #1585243) | Cod sursa (job #967125) | Cod sursa (job #2505593)
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct interval
{
int st, dr;
bool operator < (const interval A) const
{
return dr < A.dr;
}
};
interval t[100003], dp[100003];
int n, k;
int CautareBinara(int x)
{
int st, dr, p, mij;
st = 0;
dr = p = k;
while(st <= dr)
{
mij = (st + dr) / 2;
if(dp[mij].st <= x)
{
p = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
return p;
}
int main()
{
int x, y, p;
fin >> n;
for(int i = 1; i <= n; i++)
fin >> t[i].st >> t[i].dr;
fin.close();
sort(t + 1, t + n + 1);
//for(int i = 1; i <= n; i++)
// fout << t[i].st << " " << t[i].dr << "\n";
for(int i = 1; i <= n; i++)
{
x = t[i].st;
y = t[i].dr;
/// caut binar in dp cea mai din dreapta pozitie p cu dp[p].dr <= x
p = CautareBinara(x);
if(dp[k].st == y)
dp[k].dr = max(dp[k].dr, dp[p].dr + y - x);
else
{
k++;
dp[k].st = y;
dp[k].dr = max(dp[k - 1].dr, dp[p].dr + y - x);
}
}
fout << dp[k].dr << "\n";
fout.close();
return 0;
}