Cod sursa(job #169144)

Utilizator MariusGeantaMarius Geanta MariusGeanta Data 1 aprilie 2008 11:33:07
Problema Stalpi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<stdio.h>

long x[100001],c[100001],s[100001],d[100001],n,sigma;
unsigned char viz[100001],ales[100001];
long long cost;
unsigned char a[100001][100001];

void main()
{	int i,j,max,kmax,t;
	FILE  *f=fopen("stalpi.in","r");
	fscanf(f,"%d",&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[j]>=x[i]-s[i]&&x[j]<=x[i]+d[i])
				a[i][j]=1;
	while (sigma<n)
	{	max=-9999;kmax=1;
		for (i=1;i<=n;i++)
			if (!ales[i])
			{	for (j=1,t=0;j<=n;j++)
					if (viz[j]==0&&a[i][j]==1&&i!=j) t+=c[j];
				if (t-c[i]>max)
				{	max=t-c[i];kmax=i; }
			}
		ales[kmax]=1;cost+=(long long)c[kmax];
		for (i=1;i<=n;i++)
			if (a[kmax][i])
			{viz[i]=1;sigma++;}
	}
	FILE *g=fopen("stalpi.out","w");
	fprintf(g,"%lld\n",cost);
	fclose(g);
}