Cod sursa(job #1867056)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 3 februarie 2017 18:13:04
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#include <iostream>
#define MAX 100000

using namespace std;
int interval[2][MAX], timp[MAX];
void insert_sort1(int n)
{
  int i, j, aux;

  for(i = 1; i < n; i++)
  {
    j = i;
    while(j > 0 && interval[1][j] < interval[1][j - 1])
    {
      aux = interval[1][j];
      interval[1][j] = interval[1][j - 1];
      interval[1][j - 1] = aux;
      aux = interval[0][j];
      interval[0][j] = interval[0][j - 1];
      interval[0][j - 1] = aux;
      j--;
    }
  }
}
void insert_sort0(int n)
{
  int i, j, aux;

  for(i = 1; i < n; i++)
  {
    j = i;
    while(j > 0 && interval[1][j] == interval[1][j - 1] && interval[0][j] < interval[0][j - 1])
    {
      aux = interval[0][j];
      interval[0][j] = interval[0][j - 1];
      interval[0][j - 1] = aux;
      j--;
    }
  }
}
int main()
{
  FILE *fin, *fout;
  int n, i, j, maxi;

  fin = fopen("heavymetal.in", "r");
  fout = fopen("heavymetal.out", "w");
  fscanf(fin, "%d", &n);
  for(i = 0; i < n; i++)fscanf(fin, "%d%d", &interval[0][i], &interval[1][i]);
  insert_sort1(n);
  //insert_sort0(n);
  //for(i = 0; i < n; i++)printf("%d %d\n", interval[0][i], interval[1][i]);
  for(i = 0; i < n; i++)
  {
    maxi = 0;
    for(j = i - 1; j >= 0; j--)
      if(interval[0][i] >= interval[1][j] && maxi < timp[j])maxi = timp[j];
    timp[i] = maxi + interval[1][i] - interval[0][i];
  }
  maxi = 0;
  for(i = 0; i < n; i++)if(maxi < timp[i])maxi = timp[i];
  fprintf(fout, "%d", maxi);
  fclose( fin );
  fclose( fout );
  return 0;
}