Pagini recente » Cod sursa (job #3173070) | Cod sursa (job #2874565) | Cod sursa (job #2574065) | Cod sursa (job #1362696) | Cod sursa (job #916666)
Cod sursa(job #916666)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n;
int best[100010];
struct concert
{
int x, y;
};
concert a[100010];
inline void Read()
{
ifstream f ("heavymetal.in");
f>>n;
int i;
for (i=1; i<=n; i++)
f>>a[i].x>>a[i].y;
f.close();
}
inline bool cmp (const concert A, const concert B)
{
return A.y < B.y;
}
inline int Cautare_Binara(int x, int dr)
{
int rez = 0, st, mij;
st = 1;
while (st <= dr)
{
mij = (st+dr)>>1;
if (a[mij].y <= x)
st = mij + 1, rez = mij;
else
dr = mij - 1;
}
return rez;
}
inline void Solve()
{
/// best[i] = intervalul de timp maxim in care pot canta concerte din intervalul [1, i]
sort (a+1, a+n+1, cmp);
int i, poz;
for (i=1; i<=n; i++)
{
poz = Cautare_Binara(a[i].x, i-1);
/// caut binar poz = cea mai din dreapta pozitie de inceput a concertului i care
/// corespunde cu pozitia din best
best[i] = max (best[i-1], best[poz] + a[i].y - a[i].x);
}
}
inline void Write()
{
ofstream g ("heavymetal.out");
g<<best[n]<<"\n";
g.close();
}
int main()
{
Read();
Solve();
Write();
return 0;
}