Pagini recente » Cod sursa (job #2981536) | Cod sursa (job #403382) | Cod sursa (job #1109577) | Cod sursa (job #571212) | Cod sursa (job #2505595)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct Interval
{
int a, b;
bool operator < (const Interval A) const
{
return b < A.b;
}
};
Interval t[100005];
Interval dp[100005];
int n, k, x, y;
int CautBin(int x)
{
int st, dr, p, mij;
st = 0;
dr = k;
p = k;
while(st <= dr)
{
mij = (st + dr) / 2;
if(dp[mij].a <= x)
{
p = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
return p;
}
int main()
{
int i, p;
fin >> n;
for(i = 1 ; i <= n ; ++i)
fin >> t[i].a >> t[i].b;
sort(t + 1, t + n + 1);
for(i = 1 ; i <= n ; ++i)
{
x = t[i].a;
y = t[i].b;
/// caut binar in dp cea mai din dreapta pozitie p
/// cu dp[p].b <= x
p = CautBin(x);
if(dp[k].a == y) dp[k].b = max(dp[k].b, dp[p].b + y - x);
else
{
k++;
dp[k].a = y;
dp[k].b = max(dp[k - 1].b, dp[p].b + y - x);
}
}
fout << dp[k].b;
fout.close();
return 0;
}