Pagini recente » Cod sursa (job #2253259) | Cod sursa (job #108369) | Cod sursa (job #1677623) | Cod sursa (job #2644408) | Cod sursa (job #2513332)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n, tmax;
int dp[100005];
int st, dr;
struct concert
{
int a, b;
}c[100005];
bool cmp(concert a, concert b)
{
if (a.b == b.b)
return a.a < b.a;
return a.b < b.b;
}
inline int cb(int x)
{
int ans = 0;
while (st <= dr)
{
int mij = (st+dr)/2;
if (c[mij].b <= x)
{
ans = mij;
st = mij+1;
}
else
dr = mij - 1;
}
return ans;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> c[i].a >> c[i].b, tmax = max(tmax, c[i].b);
sort(c + 1, c + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
int x = c[i].a;
int y = c[i].b;
int timp = y - x;
st = 1;
dr = i;
int p = cb(x);
dp[i] = max(dp[i-1], dp[p] + timp);
}
fout << dp[n];
return 0;
}