Cod sursa(job #140670)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 22 februarie 2008 08:44:38
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <stdlib.h>
int n, best[1000], nr, ord[1000];

typedef struct
{
   int x, y;
} interv;
interv a[1000], b[1000];

int cmp(const void *a, const void *c)
{
   int x = *(int*)a, y = *(int*)c;
   if (b[x].y == b[y].y) return b[x].x - b[y].x;
   else return b[x].y - b[y].y;
}

inline max(int x, int y) {return x > y ? x : y;}

int main()
{
   freopen("heavymetal.in","r",stdin);
   freopen("heavymetal.out","w",stdout);
   int i, j, k;
   scanf("%d",&n);
   for (i = 0; i < n; i++){ scanf("%d %d",&b[i].x, &b[i].y); ord[i] = i;}
   qsort(ord,n,sizeof(int),cmp);
   for (i = 0; i < n; i++) a[i + 1] = b[ord[i]];

   for (i = 1; i <= n; i++)
   {
      if (!best[i])
      {
	 best[i] = best[i - 1];
	 for (j = i; a[j].y == a[i].y; j++)
	 {
	    for (k = i; best[k] > a[j].x; k--);
	    best[i] = max(best[i], best[k] + (a[j].y - a[j].x));
	 }
      }
   }
   printf("%d",best[n]);
   return 0;
}