Pagini recente » Cod sursa (job #1936055) | Cod sursa (job #837135) | Cod sursa (job #1890211) | Cod sursa (job #2401323) | Cod sursa (job #2988221)
#include <bits/stdc++.h>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct Interval
{
int st, dr;
}a[100005];
int Cmp(Interval A, Interval B)
{
return A.dr < B.dr;
}
int n, dp[100005];
///caut binar cea mai din dreapta pozitie cu capatul drept
///mai mic sau egal decat a[i].st
int CautBin(int x)
{
int s, d, mij, poz;
s = 1; d = n; poz = 0;
while(s <= d)
{
mij = (s + d)/2;
if(a[mij].dr <= x)
{
poz = mij;
s = mij + 1;
}
else d = mij - 1;
}
return poz;
}
int main()
{
int i;
in >> n;
for(i = 1; i <= n; i++)
{
in >> a[i].st >> a[i].dr;
}
sort(a + 1, a + 1 + n, Cmp);
for(i = 1; i <= n; i++)
{
dp[i] = dp[i - 1];
int k = CautBin(a[i].st);
dp[i] = max(dp[i], dp[k] + a[i].dr - a[i].st);
}
out << dp[n] << " ";
return 0;
}