Pagini recente » Cod sursa (job #1604097) | Cod sursa (job #710728) | Cod sursa (job #1704938) | Cod sursa (job #1463527) | Cod sursa (job #1514824)
#include <stdio.h>
#include <stdlib.h>
#define aibSize 131072
#define Nadejde 10000
#define NIL -1
typedef struct {
int v, time;
} cell;
typedef struct {
int v, next;
} list;
typedef struct {
int v, pos;
} order;
int *adj, inside;
int N, L, X, buff;
cell save[Nadejde]; // vectorul de la intrare modificat.
list l[Nadejde + 1]; // lista cu lana oilor.
int aib[aibSize + 1]; // structura heap.
order sorted[Nadejde]; // normalizam listele cu lana oilor.
/** Aloca-mi un vector de "size" + 1 elemente. **/
void alloc(int size) {
adj = (int*)calloc(size + 1, sizeof(int));
}
/** Adauga la lista "pos" valoarea "val". **/
void add(int pos, int val) {
l[++buff].v = val;
l[buff].next = adj[pos];
adj[pos] = buff;
}
/** Sorteaza crescator structura "sorted". **/
void sort(int begin, int end) {
int b = begin, e = end, pivot = sorted[(b + e) >> 1].v;
while (b <= e) {
while (sorted[b].v < pivot) {
b++;
}
while (sorted[e].v > pivot) {
e--;
}
if (b <= e) {
order tmp = sorted[b];
sorted[b++] = sorted[e];
sorted[e--] = tmp;
}
}
if (begin < e) {
sort(begin, e);
}
if (b < end) {
sort(b, end);
}
}
/** Normalizeaza lista. **/
void normalize(int size) {
int i;
for (i = 1; i <= size; i++) {
l[sorted[i].pos].v = i;
}
}
/** Insereaza in aib pozitia "x" cu valoarea "val". **/
void insert(int x, int val) {
do {
aib[x] += val;
x += x & -x;
} while (x <= aibSize);
inside += val;
}
/** Cauta binar valoarea "val" in aib. **/
int search(int val) {
int x = 0, interval;
for (interval = aibSize >> 1; interval; interval >>= 1) {
if (aib[x + interval] < val) {
val -= aib[x += interval];
}
}
return x + 1;
}
/** Da-mi cel mai mare numar disponibil din aib. **/
int maxHeap() {
int pos = search(inside);
insert(pos, NIL);
return sorted[pos].v;
}
int main(void) {
long long int sum = 0;
int i, val, pos, dist, max = 0, size = 0;
FILE *f = fopen("lupu.in", "r");
/* Citeste caracteristicile oilor. **/
fscanf(f, "%d %d %d", &N, &X, &L);
for (i = 0; i < N; i++) {
fscanf(f, "%d %d", &dist, &save[i].v);
if (dist <= X) {
save[i].time = (X - dist) / L + 1;
if (save[i].time > max) {
max = save[i].time;
}
}
}
fclose(f);
f = fopen("lupu.out", "w");
alloc(max);
/* Adauga in lista structura "save". */
for (i = 0; i < N; i++) {
if (save[i].time) {
add(save[i].time, save[i].v);
sorted[++size].v = save[i].v;
sorted[size].pos = buff;
}
}
/* Normalizeaza "sorted". */
sort(1, size);
normalize(size);
/* Calculeaza cantitatea maxima de lana pe care o poate obtine lupul. */
for (i = max; i > 0; i--) {
for (pos = adj[i]; pos; pos = l[pos].next) {
insert(l[pos].v, -NIL);
}
if (inside) {
sum += maxHeap();
}
}
fprintf(f, "%lld\n", sum);
fclose(f);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}