Pagini recente » Cod sursa (job #2213672) | Cod sursa (job #3183161) | Cod sursa (job #1600145) | Cod sursa (job #1252837) | Cod sursa (job #461548)
Cod sursa(job #461548)
#include <stdio.h>
int dist[100000],lana[100000],T[100000],viz[100000];//viz[i]=1, inseamna ca din intervalul i am luat deja o oaie
int N,X,L;
int poz(int li,int ls){
int c,i=1,j=0;
while(li<ls){
if(lana[li]<lana[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 transa(int d){
int dif=X-d;
return dif/L;
}
void bubble(int li, int ls){
int c,ok=0;
int i;
while(!ok){
ok=1;
for(i=li;i<ls;i++){
if(T[li]>T[ls]){
c=dist[li];
dist[li]=dist[ls];
dist[ls]=c;
c=lana[li];
lana[li]=lana[ls];
lana[ls]=c;
c=T[li];
T[li]=T[ls];
T[ls]=c;
ok=0;
}
}
}
}
int main(){
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]);
//indice[i]=i+1;
}
//sortez decrescator dupa lana
sortare(0,N-1);
//sortez crescator dupa distanta, si in acelasi timp asociez fiecarei distante un ti (transa din care face parte)
int li=0,ls=0;
while(ls<N){
T[ls]=transa(dist[ls]);
if(lana[li]!=lana[ls]){
bubble(li,ls-1);//sortez crescator dupa T, pe intervalul [li,ls)
//printf("sortez in intervalul [%d,%d)\n",li,ls);
li=ls;
}
ls++;
}
//o afisare
/*
for(i=0;i<N;i++){
printf("%2d ",i+1);
}
printf("\n");
for(i=0;i<N;i++){
printf("%2d ",lana[i]);
}
printf("\n");
for(i=0;i<N;i++){
printf("%2d ",T[i]);
}
printf("\n");
*/
//parcurg vectorul...
int nr_oii=0;
int g=0;
for(i=0;i<N;i++){
if(T[i]>=nr_oii){//nu am mai ales o oaie din
//viz[T[i]]=1;
nr_oii++;
//printf("aleg oaia");
//printf("%d\n",i+1);
g+=lana[i];
}
}
FILE *fout=fopen("lupu.out","w");
fprintf(fout,"%d\n",g);
}