Pagini recente » Cod sursa (job #3226392) | Cod sursa (job #3134901) | Cod sursa (job #2506287) | Cod sursa (job #3293720) | Cod sursa (job #137522)
Cod sursa(job #137522)
#include<fstream.h>
long long n,x[100000],c[100000],s[100000],d[100000],uz[100000],i,j,cost,gasit,a,b,k;
void quik(long long p,long long q)
{
long long aux,i,j,t1;
if(p<q)
{
i=p;
j=q;
t1=1;
do
{
if(c[i]>c[j])
{
aux=c[i];
c[i]=c[j];
c[j]=aux;
aux=x[i];
x[i]=x[j];
x[j]=aux;
aux=s[i];
s[i]=s[j];
s[j]=aux;
aux=d[i];
d[i]=d[j];
d[j]=aux;
t1=!t1;
}
if(t1)
j--;
else
i++;
}while(i!=j);
quik(p,i-1);
quik(i+1,q);
}
}
int main()
{
ifstream f("stalpi.in");
ofstream g("stalpi.out");
f>>n;
for(i=1;i<=n;i++)
f>>x[i]>>c[i]>>s[i]>>d[i];
quik(1,n);
i=0;
while(!gasit)
{
i++;
gasit=1;
cost+=c[i];
for(k=1;k<=i;k++)
{
a=x[k]-s[k];
b=x[k]+d[k];
for(j=i+1;j<=n;j++)
if(x[j]>=a&&x[j]<=b)
uz[j]=1;
}
for(j=i+1;j<=n;j++)
if(uz[j]==0)
gasit=0;
if(i==n)
gasit=1;
for(j=i+1;j<=n;j++)
uz[j]=0;
}
g<<cost;
return 0;
}