Cod sursa(job #461472)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 6 iunie 2010 22:12:18
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>

int dist[100],lana[100];

int poz(int li,int ls){
   int c,i=1,j=0;
   while(li<ls){
     if(dist[li]<dist[ls]){
	  c=dist[li];
	  dist[li]=dist[ls];
	  dist[ls]=c;

	  c=lana[li];
	  lana[li]=lana[ls];
	  lana[ls]=c;

	  c=i;
	  i=-j;
	  j=-c;
       }
   li+=i;
   ls+=j;
   }
   return li;
}

void sortare(int li,int ls){
   int k;
   if(li<ls){
     k=poz(li,ls);
     sortare(li,k-1);
     sortare(k+1,ls);
   }
}

int main(){
  int N,X,L;
  int i;
  FILE *fin=fopen("lupu.in","r");
  fscanf(fin,"%d%d%d",&N,&X,&L);
  for(i=0;i<N;i++)
    fscanf(fin,"%d%d",&dist[i],&lana[i]);
  //sortez decrescator dupa distanta
  sortare(0,N-1);
  int limita=0;
  int ok=0,max,suma=0;
  while(!ok){
     //de unde(poz inclusiva) trebuie sa incep sa caut max(oi la care ajung)
     ok=1;max=-1;
     for(i=limita;(i<N)&&ok;i++){
	if(dist[i]+L<=X){
	     ok=0;
	     limita=i;
	}else {
	    if(lana[i]>max)max=lana[i];
	}
     }
     suma+=max;
     for(i=limita;i<N;i++)dist[i]+=L;
  }
   FILE *fout=fopen("lupu.out","w");
   fprintf(fout,"%d\n",suma);
return 0;
}