Cod sursa(job #2049809)

Utilizator b0gd4nBogdan b0gd4n Data 27 octombrie 2017 17:41:40
Problema Heavy metal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#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(-1);

  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;
}