Pagini recente » Cod sursa (job #2898066) | Cod sursa (job #1374602) | Cod sursa (job #276473) | Cod sursa (job #2758147) | Cod sursa (job #2121650)
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
#define lim 100010
int n, pos;
struct formatie {int st,dr;} ini[lim];
int rez, dp[lim]; /// dp[i] = suma max obtinuta daca ultimul concert are capatul <= ini[i].dr
bool cmp (formatie A, formatie B)
{
if (A.dr<B.dr) return 1;
if (A.dr==B.dr) return (A.st<B.st);
return 0;
}
/// cea mai mare p<=x care are ini[p].dr <= ini[x].st
int b_s (int x)
{
int mask=0, p;
for (mask=1; mask<=x; mask<<=1);
for (p=0; mask>0; mask>>=1)
if (p+mask <= x)
if (ini[p+mask].dr <= ini[x].st) p+=mask;
return p;
}
int main()
{
fin>>n;
for (int i=1; i<=n; i++) fin>>ini[i].st>>ini[i].dr;
sort (ini+1, ini+n+1, cmp);
for (int i=1; i<=n; i++)
{
pos = b_s (i);
dp[i] = max (dp[i-1], dp[pos]+ini[i].dr-ini[i].st);
rez = max (rez, dp[i]);
}
fout<<rez;
fout.close();
return 0;
}