Pagini recente » Cod sursa (job #1860905) | Cod sursa (job #2231901) | Clasamentul arhivei de probleme | Borderou de evaluare (job #587466) | Cod sursa (job #443210)
Cod sursa(job #443210)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int *greu;
int *high;
int *time;
int *best;
int n,U,H;
void exchange(int a, int b)
{
int j;
j=time[a];
time[a]=time[b];
time[b]=j;
j=greu[a];
greu[a]=greu[b];
greu[b]=j;
}
void quickSort (int lo, int hi)
{
int i=lo, j=hi, h;
int x=time[(lo+hi)/2];
while (i<=j)
{
while (time[i]<x)
i++;
while (time[j]>x)
j--;
if (i<=j)
{
exchange(i,j);
i++;
j--;
}
}
if (lo<j) quickSort(lo, j);
if (i<hi) quickSort(i, hi);
}
void testQuickSort()
{
int i;
quickSort(0,n-1);
for(i=0;i<n;i++)
printf("%d ",time[i]);
}
int getmin(int k)
{
int min,i;
min = k;
for (i=k; i>=0; i--){
if (best[min]>best[i])
min=i;
}
return min;
}
void printVec(int *a)
{
int i;
for (i=0; i < n; i++)
printf("%d ",a[i]);
puts("");
}
int main()
{
FILE *fp;
fp=fopen("gutui.in","r");
int i;
fscanf(fp,"%d %d %d", &n, &H, &U);
greu = (int *) calloc (n,sizeof(int));
high = (int *) calloc (n,sizeof(int));
time = (int *) calloc (n,sizeof(int));
for (i=0; i<n; i++)
{
fscanf(fp,"%d %d", &high[i], &greu[i]);
greu[i] = greu[i];
high[i] = high[i];
}
for (i=0; i<n; i++)
time[i]= (H-high[i])/U;
/* printf("\nAFISARE GREUTATI\n");
for (i=0; i<n; i++)
printf("%d\n",greu[i]);
*/
quickSort(0,n-1);
close(fp);
best = (int *) calloc(n,sizeof(int));
int pos;
for (i=0; i<n; i++)
{
pos = getmin(time[i]);
// printf("pos=%d\n", pos);
if (best[pos] < greu[i])
best[pos] = greu[i];
// printf("i=%d\n",i);
//printVec(best);
}
//printf("\nAFISARE TIMPI\n");
/*for (i=0; i<n; i++)
printf("%d ", time[i]);
printf("\n");
//printf("\n AFISARE TIMPI SI GREUTATI ORDONATI\n");
/*for (i=0; i<n; i++)
{
printf("G:%d T:%d ",greu[i], time[i]);
printf("\n");
}
//printf("\nAFISARE vector best\n");
//printVec(best);
*/
fp=fopen("gutui.out","w");
int sum;
sum=0;
for (i=0; i<n; i++)
sum+=best[i];
fprintf(fp,"%d",sum);
fclose(fp);
return 0;
}