Pagini recente » Cod sursa (job #1182404) | Cod sursa (job #627152) | Cod sursa (job #2729180) | Cod sursa (job #2730423) | Cod sursa (job #434353)
Cod sursa(job #434353)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100001
typedef struct item {
long int poz;
long int val;
item *next;
} item;
item *p, *l;
void adauga (long int j, long int gr) {
item *nou = new item;
nou->poz = j; nou->val = gr; nou->next = NULL;
if (j <= p->poz) {
nou->next = p; p = nou; return;
}
if (j >= l->poz) {
l->next = nou; l = nou; return;
}
item *a, *b; a = p; b = p->next;
while (j > b->poz) {
a = b;
b = b->next;
}
nou->next = b;
a->next = nou;
}
long int min (long int v[NMAX], long int n) {
long int minim = n;
long int i;
for (i=n-1; i>0; i--) {
if (v[i] == 0) {
return i;
}
if (v[i] < v[minim]) {
minim = i;
}
}
return minim;
}
int main () {
FILE *f, *g;
long int n, hmax, u, h, gr, 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", &gr);
p = new item; l = new item;
p->poz = (hmax-h)/u + 1; p->val = gr; p->next = NULL; l = p;
for (i=2; i<=n; i++) {
fscanf (f, "%ld", &h);
fscanf (f, "%ld", &gr);
j = (hmax - h)/u + 1;
adauga (j, gr);
}
while (p != NULL) {
if (v[p->poz] == 0) {
s = s+p->val;
v[p->poz] = p->val;
}
else {
long int k = min (v, p->poz);
if (p->val > v[k]) {
s = s-v[k]+p->val;
v[k] = p->val;
}
}
p = p->next;
}
fprintf (g, "%ld", s);
fclose (f); fclose (g);
return 0;
}