Pagini recente » Cod sursa (job #519379) | Cod sursa (job #1163865) | Cod sursa (job #1975468) | Cod sursa (job #2691988) | Cod sursa (job #434388)
Cod sursa(job #434388)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100001
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++;
}
}
void adauga (long int v[NMAX], long int val, long int n) {
while ((val > v[n-1]) && (n>1)) {
v[n] = v[n-1];
n--;
}
v[n] = val;
}
void insereaza (long int nivel[NMAX], long int gr[NMAX], long int j, long int val, int n) {
while ((j > nivel[n-1]) && (nivel[n-1] != 0)){
nivel[n] = nivel[n-1];
gr[n] = gr[n-1];
n--;
}
while ((j == nivel[n-1]) && (val > gr [n-1])) {
nivel[n] = nivel[n-1];
gr[n] = gr[n-1];
n--;
}
nivel[n] = j;
gr[n] = val;
}
int main () {
FILE *f, *g;
long int n, hmax, u, h, val, s=0, i, j, nivel[NMAX], gr[NMAX], v[NMAX];
f = fopen ("gutui.in", "r");
g = fopen ("gutui.out", "w");
fscanf (f, "%ld", &n);
fscanf (f, "%ld", &hmax);
fscanf (f, "%ld", &u);
for (i=1; i<=n; i++) {
fscanf (f, "%ld", &h);
fscanf (f, "%ld", &val);
j = (hmax-h)/u + 1;
insereaza (nivel, gr, j, val, i);
}
i = 1; long int index = nivel[1];
while (nivel[i] == index) {
v[i] = gr[i];
s += gr[i];
i++;
}
index--;
long int max;
while ((index > 0) && (i<=n)) {
max = index;
while (nivel[i] == index) {
if ((gr[i] < v[n]) || (max == 0))
i++;
else {
s = s-v[n]+gr[i];
adauga (v, gr[i], n);
i++;
max--;
}
}
index--;
}
fprintf (g, "%ld", s);
fclose (f); fclose (g);
return 0;
}