Pagini recente » Cod sursa (job #229631) | Cod sursa (job #1050869) | Cod sursa (job #794952) | Cod sursa (job #2068626) | Cod sursa (job #2049819)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f, *g;
#define MAXN 100003
struct concert
{
int A, B;
};
int N, A, B;
int Tmax; //Timpul maxim de terminare a unui concert.
//Memorez intervalele concertelor.
vector<concert> C;
//Best[i]=timpul total maxim in care vor canta formatii daca fiecare concert se va termina inainte de ora i.
//vector<int> Best;
int Best[1 << 17];
int a[MAXN];
int b[MAXN];
concert Make (int A, int B)
{
concert r = {A, B};
return r;
}
bool How (concert c1, concert c2)
{
return c1.B < c2.B;
}
int Search(int k)
{
//Niciun spectacol nu s-a terminat inainte sa inceapa acesta.
if( C[1].B > C[k].A )
return 0;
int st=1;
int dr=k-1;
int mij=(st+dr)/2;
while (true)
{
if(st+1==dr){
if(C[dr].B <= C[k].A)return dr;
else if(C[st].B <= C[k].A) return st;
}
if(st==dr && C[mij].B <= C[k].A)return mij;
if(C[k].A == C[mij].B) {
return mij;
}
else if (C[mij].B > C[k].A){
dr=mij-1;
}
else if (C[mij].B < C[k].A){
st=mij;
}
mij=(st+dr)/2;
}
}
int main()
{
f = fopen ("heavymetal.in", "r");
g = fopen ("heavymetal.out", "w");
fscanf (f, "%d", &N);
C.push_back (Make (0, 0) );
for (int i = 1; i <= N; i++)
{
fscanf (f, "%d %d", &A, &B);
C.push_back (Make (A, B) );
//Tmax = max (Tmax, B);
}
//Sortez crescator dupa campul B.
sort (C.begin(), C.end(), How);
//for (int i = 0; i < N; i++) cout << C[i].A << " " << C[i].B << endl;
//Best.push_back (0);
/*for (int i = 1; i <= Tmax; i++)
{
Best.push_back(Best[i-1]);
for (int j = 0; j < N; j++)
{
if (C[j].B == i) Best[i] = max(Best[i], Best[C[j].A] + (C[j].B - C[j].A));
else if (C[j].B > i) break;
}
}
*/
Best[1] = C[1].B - C[1].A;
for (int k = 2; k <= N; k++)
{
Best[k] = Best[k - 1];
int caut = Search(k);
//Caut pozitia din C a spectacolului care se terina mai repede sau egal cu timpul
//de start spectacolului din C de pe pozitia K, adica C[k].A in O(N).
/*for (int j = k - 1; j >= 1; j--)
if (C[j].B <= C[k].A)
{
caut = j;
break;
}
*/
//Caut binar.
//if (caut == -1) Best[k] = max(Best[k], (C[k].B - C[k].A)); //Nu am gasit un alt concert care sa fi avut loc inainte.
//else
Best[k] = max (Best[k], Best[caut] + (C[k].B - C[k].A) );
Tmax = max(Tmax, Best[k]);
}
//for (int i = 0; i <= Tmax; i++) cout << i << "=" << Best[i] << endl;
fprintf (g, "%d", Tmax);
fclose (f);
fclose (g);
return 0;
}