Pagini recente » Cod sursa (job #351174) | Cod sursa (job #654240) | Cod sursa (job #2191960) | Cod sursa (job #2403697) | Cod sursa (job #3131117)
#include <bits/stdc++.h>
#define N 100000
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct concert
{
int st;
int dr;
} a[N + 5];
int n;
long long timp_max[N + 5]; /// timp_max[i] = timpul maxim in care se canta daca aleg din primele i concerte
int timp_final[N + 5]; /// timp_final[i] = ora la care se termina daca alaeg timpul maxim din primele i
void Citire()
{
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> a[i].st >> a[i].dr;
}
inline bool comp(concert x, concert y) /// sortam cresc dupa capatul din dreapta
{
return x.dr < y.dr || (x.dr == y.dr && x.st < y.st);
}
int CB(int st, int dr, int x)
{
/// cautam cea mai din dreapta pozitie pt care timp_final[i] <= a[i].st (x)
int possible = -1;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(timp_final[mij] <= x) possible = mij, st = mij + 1;
else dr = mij - 1;
}
return possible;
}
void Rezolvare()
{
timp_max[1] = a[1].dr - a[1].st;
timp_final[1] = a[1].dr;
for(int i = 2; i <= n; ++i)
{
/// daca pot sa l alatur celelorlate concerte, o fac
int p = CB(1, i - 1, a[i].st);
if(p != -1)
{
timp_max[i] = timp_max[p] + (a[i].dr - a[i].st);
timp_final[i] = a[i].dr;
}
else
{
/// verific daca e mai avantajos sa le pastez pe celelalte
if(timp_max[i - 1] >= (a[i].dr -a[i].st))
timp_max[i] = timp_max[i - 1], timp_final[i] = timp_final[i - 1];
else
timp_max[i] = a[i].dr - a[i].st, timp_final[i] = a[i].dr;
}
}
fout << timp_max[n];
}
int main()
{
Citire();
sort(a + 1, a + n + 1, comp);
Rezolvare();
return 0;
}