Pagini recente » Cod sursa (job #402711) | Cod sursa (job #443692) | Cod sursa (job #852865) | Cod sursa (job #672927) | Cod sursa (job #434196)
Cod sursa(job #434196)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100001
typedef struct item {
long int nivel;
long int gr;
item *next;
} item;
void adauga1 (long int v[NMAX], long int val, long int n) {
v[n] = val;
long int i=n;
while ((val < v[i-1]) && (i>0)){
v[i] = v[i-1];
v[i-1] = val;
i--;
}
}
void adauga2 (long int v[NMAX], long int val, long int n) {
long int i=1;
v[1] = val;
while ((val > v[i+1]) && (i<n)) {
v[i] = v[i+1];
v[i+1] = val;
i++;
}
}
item * insereaza (item *p, long int j, long int val) {
item *nou = new item; nou->nivel = j; nou->gr = val; nou->next = NULL; //creare element nou
if ((j < p->nivel) || ((j == p->nivel) && (val > p->gr))) { //daca nivelul e minim si inexistent sau valoare de introdus e pe primul nivel
nou->next = p;
p = nou;
return p;
}
item *aux = new item; aux = p;
while ((aux->next != NULL) && (j > aux->next->nivel))
aux = aux->next;
if (aux->next == NULL) { //nivelul pe care vreau sa-l introduc e mai mare decat celelalte
aux->next = nou;
return p;
}
if (j < aux->next->nivel) { //nivelul nu exista dar nu este cel mai mare
nou->next = aux->next;
aux->next = nou;
return p;
}
//nivelul exista
while ((aux->next->nivel == j) && (val < aux->next->gr))
aux = aux->next;
if (aux->next == NULL) { //valoare e cea mai mica de pe cel mai mare nivel
aux->next = nou;
return p;
}
nou->next = aux->next; aux->next = nou;
return p;
}
int main () {
FILE *f, *g;
long int n, hmax, u, h, val, s=0, i, j, v[NMAX];
f = fopen ("gutui.in", "r");
g = fopen ("gutui.out", "w");
fscanf (f, "%ld", &n);
fscanf (f, "%ld", &hmax);
fscanf (f, "%ld", &u);
fscanf (f, "%ld", &h);
fscanf (f, "%ld", &val);
item *p = new item; p->gr = val; p->nivel = (hmax-h)/u + 1;
for (i=2; i<=n; i++) {
fscanf (f, "%ld", &h);
fscanf (f, "%ld", &val);
j = (hmax-h)/u + 1;
p = insereaza (p, j, val);
}
int index = 0;
while (p != NULL) {
if (index < p->nivel) {
s += p->gr;
index++;
adauga1 (v, p->gr, index);
}
else
if (p->gr > v[1]) {
s = s - v[1] + p->gr;
adauga2 (v, p->gr, index);
}
p=p->next;
}
fprintf (g, "%ld", s);
fclose (f); fclose (g);
return 0;
}