Cod sursa(job #2049683)

Utilizator b0gd4nBogdan b0gd4n Data 27 octombrie 2017 15:34:26
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 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 main()
{
  f = fopen ("heavymetal.in", "r");
  g = fopen ("heavymetal.out", "w");

  fscanf (f, "%d", &N);
  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[0] = C[0].B - C[0].A;
  for (int k = 1; k < N; k++)
  {
    Best[k] = Best[k - 1];

    int caut = C[k].A;

    for (int j = k - 1; j >= 0; j--)
      if (C[j].B <= caut)
      {
        caut = j; break;
      }

    Best[k] = max (Best[k], Best[caut] + (C[k].B - C[k].A) );

  }
  //for (int i = 0; i <= Tmax; i++) cout << i << "=" << Best[i] << endl;

  fprintf (g, "%d", Best[N - 1]);

  fclose (f);
  fclose (g);

  return 0;
}