Pagini recente » Cod sursa (job #467693) | Cod sursa (job #42607) | Cod sursa (job #1450567) | Cod sursa (job #147865) | Cod sursa (job #169144)
Cod sursa(job #169144)
#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);
}