Cod sursa(job #438643)

Utilizator minwooMinulescu Alexandru minwoo Data 10 aprilie 2010 22:18:35
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.61 kb
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct {
        unsigned long int h,g;
        } gutui;

int main(int argc, char *argv[])
{
  unsigned long int n, hmax, u, deltah = 0, i, j, sum=0;
  FILE* f = fopen("gutui.in", "r");
  fscanf(f,"%lu", &n);
  fscanf(f,"%lu", &hmax);
  fscanf(f,"%lu", &u);
  gutui a[100000],  candidat, aux; 
  for (i=1;i<=n;i++) 
      fscanf(f,"%lu %lu", &a[i].h, &a[i].g);
    for (i=1; i <= n; i++)
  {
      
      int j;
      gutui v = a[i];

      for (j = i - 1; j >= 1; j--)
      {
          if ((a[j].h+u) < v.h) break;
          if ((a[j].h == v.h) || (a[j].h-v.h<u)) if (a[j].g<v.g) break;
          a[j + 1] = a[j];
      }
      a[j + 1] = v;

  }
  //for (i=1; i<=n; i++) printf("a[%d]: %d %d \n", i, a[i].h, a[i].g);
  candidat=a[n];
  hmax-=u;
  sum+=candidat.g;
  for (i=n-1;i>0;i--) {
      deltah=candidat.h-a[i].h;
      //printf("i:%d h=%d g=%d candidat.h=%d candidat.g=%d hmax=%d deltah=%d sum=%d\n", i, a[i].h, a[i].g, candidat.h, candidat.g, hmax, deltah, sum);
      if (deltah>=u) {
      hmax-=u;
      
      sum+=candidat.g;
      candidat=a[i];
      } else if (deltah==0 && hmax>a[i].h) {
                                 hmax-=u;
                                 sum+=a[i].g;
                                  
                
             }
      else if (a[i].g>candidat.g) candidat=a[i];
           
             
      
  }
  sum+=candidat.g;
  //printf("suma: %d", sum); 
   FILE* g=fopen("gutui.out", "w");
  fprintf(g,"%lu",sum);
  //system("PAUSE");	
  fclose(f);
  fclose(g);
  return 0;
}