Cod sursa(job #439374)

Utilizator beletteodorTeo Belet beletteodor Data 11 aprilie 2010 15:44:20
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 3.55 kb
#include<stdio.h>
#include<stdlib.h>

//interschimba 2 elemente din vectorul de gutui
void swap (int* inaltime_a, int* greutate_a, int* inaltime_b, int* greutate_b) {
    int aux_a, aux_b;
    aux_a = *inaltime_a;
    *inaltime_a = *inaltime_b;
    *inaltime_b = aux_a;
    aux_b = *greutate_a;
    *greutate_a = *greutate_b;
    *greutate_b = aux_b;
}

//functie ajutatoare pentru functia de sortare quicksort
int mid (int i, int j) {
    return ((i + j) / 2);
}

//sorteaza descrescator in functie de greutate in vectorul de gutui
void quicksort (int* inaltime, int* greutate, int m, int n) {   
    int key, i, j, k;
    if (m < n) {
       k = mid (m, n);
       swap (&inaltime[m], &greutate[m], &inaltime[k], &greutate[k]);
       key = greutate[m];
       i = m + 1;
       j = n;
       while (i <= j) {
             while ((i <= n) && (greutate[i] >= key))
                   i++;
             while ((j >= m) && (greutate[j] < key))
                   j--;
             if (i < j)
                swap (&inaltime[i], &greutate[i], &inaltime[j], &greutate[j]);
       }
       swap (&inaltime[m], &greutate[m], &inaltime[j], &greutate[j]);
       quicksort (inaltime, greutate, m, j - 1);
       quicksort (inaltime, greutate, j + 1, n);
    }
}

int main() {
//declarari variabile
    int N, H, U, i, j, ok = 0, count = -1, local;
    freopen ("gutui.in", "r", stdin);
    freopen ("gutui.out", "w", stdout);
    scanf ("%d", &N);
//alocare memorie
    int* inaltime = (int*) malloc (N * sizeof (int)); 
    int* greutate = (int*) malloc (N * sizeof (int)); 
    int* order = (int*) malloc (N * sizeof (int));
    int* maximum = (int*) malloc (N * sizeof (int));
    int* iso = (int*) malloc (N * sizeof (int));
//citire din fisier
    scanf ("%d%d", &H, &U);
    for ( i = 0; i < N; i++)
        scanf ("%d%d", &inaltime[i], &greutate[i]);
    /*for (i=0;i<N;i++)
        printf("%d %d\n",inaltime[i],greutate[i]);
    printf("\n");*/
    quicksort (inaltime, greutate, 0, N - 1);
//formare vector order   
    for (i = 0; i < N; i++) {
        if (inaltime[i] > H)
           order[i] = -1;
        else
           order[i] = (H - inaltime[i]) / U;
    }
    for (i = 0; i < N; i++)
        if (order[i] != -1) {
           if (i == 0) {
              maximum[++count] = order[i];
              iso[count] = order[i] + 1;
              ok = ok + greutate[i];
              iso[count]--;
           }
           else {
              if (order[i] > maximum[count]) {
                 maximum[++count] = order[i];
                 iso[count] = maximum[count] - maximum[count - 1];
                 ok = ok + greutate[i];
                 iso[count]--;
              }
              else {
                 local = -1;
                 for (j = 0; j <= count; j++) {
                     if (j == 0 && order[i] >= 0 && order[i] <= maximum[j])
                        local = 0;
                     if (j != 0 && order[i] > maximum[j - 1] && order[i] <= maximum[j])
                        local = j;
                     if (local != -1)
                        break;
                 }
                 while (local >= 0) {
                       if (iso[local] > 0) {
                          ok = ok + greutate[i];
                          iso[local]--;
                          break;
                       }
                       else
                          local--;
                 }
                               
              }
           }
        }
    printf ("%d\n", ok);     
    return 0;
}