Cod sursa(job #137358)

Utilizator rethosPaicu Alexandru rethos Data 17 februarie 2008 11:36:06
Problema Stalpi Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasa a 10-a Marime 0.88 kb
#include <stdio.h>
#define NMAX 101
FILE *f=fopen("stalpi.in","rt");
FILE *g=fopen("stalpi.out","wt");
long x[NMAX],s[NMAX],d[NMAX],c[NMAX],n,a[NMAX][NMAX],viz[NMAX];
long long suma;
int exista(long x)
{ long i;
  for (i=1;i<=a[x][0];i++)
	if (viz[a[x][i]]==0) return 1;
  return 0;
}
long costmin()
{ long min,i,k;
  min=10000;
  for (i=1;i<=n;i++)
	if (c[i]<min&&exista(i))
		{ min=c[i];
		  k=i;
		}
  if (min==10000) return 0;
  return k;
}
int main()
{ long j,k,i;
  fscanf(f,"%ld",&n);
  for (i=1;i<=n;i++) fscanf(f,"%ld %ld %ld %ld",&x[i],&c[i],&s[i],&d[i]);
  fclose(f);
  for (i=1;i<=n;i++) for (j=1;j<=n;j++)
			if (x[i]-s[i]<=x[j]&&x[j]<=x[i]+d[i])
				a[i][++a[i][0]]=j;
  suma=0;
  k=costmin();
  while (k)
	{ suma+=c[k];
	  viz[k]=1;
	  for (i=1;i<=a[k][0];i++) viz[a[k][i]]=1;
	  k=costmin();
	}
  fprintf(g,"%lld",suma);
  fclose(g);
  return 0;
}