Pagini recente » Cod sursa (job #1544602) | Cod sursa (job #2752328) | Cod sursa (job #1214534) | Cod sursa (job #1754136) | Cod sursa (job #436882)
Cod sursa(job #436882)
//STOICA GEORGE CRISTIAN 325CA
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
//structura pentru gutui cu inaltimea, greutatea si nivelul pe care se afla
typedef struct
{
long h;
long g;
long l;
} gutui;
long u;
long h;
//structura pentru retinerea pozitiei la care incepe fiecare nivel si numarul nivelului
typedef struct
{
long l;
long poz;
} level;
//ordonez vectorul de gutui in functie de nivel, si pe acelasi nivel in functie de greutate
int compare(const void* a, const void* b)
{
gutui* a1 = (gutui *)a;
gutui* b1 = (gutui *)b;
long k = a1->l;
long t = b1->l;
if (k == t) return (-(a1->g) + (b1->g));
else return (k - t);
}
int main()
{
long n;
FILE *f = fopen("gutui.in","r");
FILE *ff = fopen("gutui.out","w");
fscanf(f,"%ld %ld %ld",&n, &h, &u);
long i;
long g = 0;
gutui *a = (gutui *)calloc(n,sizeof(gutui));
long nr = 0;
long maxLevel = -1;
for (i=0; i<n; i++)
{
fscanf(f,"%ld %ld",&a[i].h, &a[i].g);
a[i].l = (long)((h-(a[i].h))/u); //retin nivelul pe care se afla gutuia
if (a[i].l > maxLevel)
maxLevel = a[i].l; //retin nivelul maxim pe care se gaseste minim o gutuie
}
qsort (a, n, sizeof(gutui), compare); //ordonez vector a cu functia compare
long t=-1;
for (i=0; i<n; i++)
if (a[i].l>t)
{
nr++; //calculez numarul total de nivele pe care se gasesc gutui
t = a[i].l;
}
level * b = (level *) calloc (nr, sizeof(level)); //vectorul care imi retine pntru fiecare nivel pe care se afla
//minim o gutuie, nivelul respectiv si pozitia sa de inceput in vectorul de gutui
long l = -1;
long j = 0;
for (i=0; i<n; i++)
if (a[i].l > l)
{
b[j].l = a[i].l;
b[j].poz = i; //completez vectorul b
j++;
l = a[i].l;
}
//heapul in care voi avea maxim maxLevel gutui, cele care vor fi culese
long *heap = (long *) calloc(maxLevel, sizeof(long));
//marimea heapului, care la un nivel L poate fi maxim L+1
long size = 0;
for (i = 0; i<nr; i++)
{
long l = b[i].l;
long j = b[i].poz;
int ok = 1;
while (ok)
{
if (j-b[i].poz>l) break;
if (a[j].l == l)
{
if (size <l+1)
{
heap[size++] = -a[j].g;
push_heap(heap, heap+size);
}
else
if (-a[j].g < heap[0])
{
pop_heap(heap,heap+size);
heap[size-1] = -a[j].g;
push_heap(heap,heap+size);
}
}
else ok = 0;
j++;
}
}
for (i=0; i<size; i++)
g+= (-heap[i]);
fprintf(ff,"%ld",g);
fclose(f);
fclose(ff);
return 0;
}