Cod sursa(job #137349)

Utilizator lamez0rBogdan Bondor lamez0r Data 17 februarie 2008 11:30:06
Problema Stalpi Scor 0
Compilator c Status done
Runda preONI 2008, Runda 4, Clasele 11-12 Marime 1.46 kb
#include<stdio.h>
long nr,n,cmin=0;

struct stalp
       {
       long x,c,s,d;
       }st[1000];

void citire ()
     {
     long i;
     FILE *f;
     f=fopen("stalpi.in","r");
     fscanf(f,"%ld",&n);
     for (i=1;i<=n;++i)
	 {
	 fscanf(f,"%ld%ld%ld%ld",&st[i].x,&st[i].c,&st[i].s,&st[i].d);
	 }
     fclose(f);
     }

int pozitie (int l, int r)
    {
    int y=st[l].x,f=st[l].c,g=st[l].s,h=st[l].d;
    while (l<r)
	  {
	  while (l<r&&y<=st[r].x)
		--r;
	  st[l].x=st[r].x;
	  st[l].c=st[r].c;
	  st[l].s=st[r].s;
	  st[l].d=st[r].d;
	  while (l<r&&y>=st[l].x)
		++l;
	  st[r].x=st[l].x;
	  st[r].c=st[l].c;
	  st[r].s=st[l].s;
	  st[r].d=st[l].d;
	  }
    st[l].x=y;
    st[l].c=f;
    st[l].s=g;
    st[l].d=h;
    return l;
    }

void quick (int l, int r)
     {
     long p;
     p=pozitie(l,r);
     if (l<p-1)
	quick(l,p-1);
     if (p+1<r)
	quick(p+1,r);
     }

void solve ()
     {
     long i,bec=2,cost,initial=1;
     while (bec<=n)
	 {
	 if (st[bec].x-st[bec].s<=st[initial].x)
	    {
	    ++bec;
	    }
	 else
	    {
	    cost=10000;
	    for (i=1;i<=bec-1;++i)
		if (st[i].c<cost)
		   {
		   cost=st[i].c;
		   initial=i+1;
		   }
	    cmin+=cost;
	    bec=i+2;
	    }
	 }
     }

void afisare ()
     {
     FILE *f;
     f=fopen("stalpi.out","w");
     fprintf(f,"%ld",cmin);
     fclose(f);
     }

int main ()
{
citire();
nr=n;
quick (1,n);
solve ();
afisare ();
return 0;
}