Pagini recente » Clasament oni_check | Cod sursa (job #2057763) | Cod sursa (job #1322259) | Cod sursa (job #1733181) | Cod sursa (job #169145)
Cod sursa(job #169145)
#include<stdio.h>
long x[1001],c[1001],s[1001],d[1001],n,sigma;
unsigned char viz[1001],ales[1001];
long long cost;
unsigned char a[1001][1001];
int 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);
return 0;
}