Pagini recente » Cod sursa (job #2350926) | Cod sursa (job #2745585) | Cod sursa (job #829254) | Cod sursa (job #3192339) | Cod sursa (job #1219651)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
const int nmax=100005;
int n,i,j,v[nmax],p;
struct spectacol {int bg,end;};
spectacol a[nmax];
// ok , deci spirul la problema asta ii sa ordonam crescator spectacolele in ordinea terminarii lor.
bool cmp (spectacol A,spectacol B)
{
if (A.end!=B.end)
return A.end<B.end;
}
int binsearch (int val)
{
int step,rez=0;
for (step=1;step<=n;step<<=1);
for (rez=0;step;step>>=1)
if (rez+step<=n && a[rez+step].end<=val)
rez+=step;
return rez;
}
int main()
{ // vom lua un vector v , pt care v[i] = durata maxima de concert pana la al i-lea spectacol
f>>n;
for (i=1;i<=n;i++)
f>>a[i].bg>>a[i].end;
sort(a+1,a+n+1,cmp);
v[1]=a[1].end-a[1].bg;
for (i=2;i<=n;i++)
{
p=binsearch(a[i].bg);
v[i]=max(v[i-1],a[i].end-a[i].bg+v[p]); // aici facem urmatorul calcul , luam spectacolul actual sau nu ? daca nu , luam timpul dinainte , daca da , vom lua spectacolul actual + v[j] , unde j este spectacolul chiar din fata celui actual (adica primul spectacol cu care n use suprapune)
}
g<<v[n];
return 0;
}