Cod sursa(job #1016256)

Utilizator Raducu1992Raducu Raducu1992 Data 25 octombrie 2013 22:46:22
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.83 kb
#include <stdio.h>
#include<stdlib.h>
struct gutui
{
    int greutate,inaltime;
};
int N,H,U,greutateFinal=0;
struct gutui *v;
void Date()
{
    int i;
    FILE *f = fopen("gutui.in", "r");
    fscanf(f, "%d%d%d",&N,&H,&U);
    v = (struct gutui*)malloc(N*sizeof(struct gutui));
    for(i = 0; i < N; ++i)
    {
        fscanf(f, "%d", &v[i].inaltime);
        fscanf(f, "%d", &v[i].greutate);
    }
    fclose(f);
}
void interschimb(int a,int b)
{
    int retineH,retineG;
      retineH = v[a].inaltime;
      retineG = v[a].greutate;
      v[a].inaltime = v[b].inaltime;
      v[a].greutate = v[b].greutate;
      v[b].inaltime = retineH;
      v[b].greutate = retineG;

}
void Qsort(int st,int dr)
{
    int pivH,i,j,mid;
    if( st < dr)
    {
        mid = (st+dr)/2;
        interschimb(st,mid);
        pivH = v[st].inaltime;
        i = st+1;
        j = dr;
        while(i <= j)
        {
            while((i <= dr) && (v[i].inaltime <= pivH))
                i++;
            while((j >= st) && (v[j].inaltime > pivH))
                j--;
            if( i < j)
                interschimb(i,j);
        }
        interschimb(st,j);
        Qsort(st,j-1);
        Qsort(j+1,dr);
    }
}
void scrieDate()
{
    FILE *f = fopen("gutui.out","w");
     fprintf(f,"%d",greutateFinal);
    fclose(f);
}
int cresteH(int k)
{
    int i;
    for(i = k; i >= 0; i--)
    {
        v[i].inaltime += U;
        if(v[i].inaltime > H)
            return 0;
    }
    return 1;
}
int main()
{
    int k;
    Date();
    Qsort(0,N-1);
    k = N-1;
    while( k >= 0 )
    {
        if( v[k].inaltime <= H)
        {
            greutateFinal += v[k].greutate;
            if( cresteH(k-1) == 0 )
                k = -1; // break;
        }
        k--;
    }
    scrieDate();
 return 0;
}