Pagini recente » Cod sursa (job #1838098) | Cod sursa (job #682845) | Cod sursa (job #2644539) | Cod sursa (job #2822571) | Cod sursa (job #436775)
Cod sursa(job #436775)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
typedef struct
{
long h;
long g;
long l;
} gutui;
long u;
long h;
typedef struct
{
long l;
long poz;
} level;
int compare(const void* a, const void* b)
{
gutui* a1 = (gutui *)a;
gutui* b1 = (gutui *)b;
long k = a1->l;
long t = b1->l;
//printf("%ld %ld (%ld) (%ld)\n",k, t, a1->h, b1->h);
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 max = -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);
if (a[i].l > max)
max = a[i].l;
}
qsort (a, n, sizeof(gutui), compare);
long t=-1;
for (i=0; i<n; i++)
if (a[i].l>t)
{
nr++;
t = a[i].l;
}
/* for (i=0; i<n; i++)
printf("**%ld %ld %ld\n",a[i].h,a[i].g, a[i].l);
printf("^^^^ %ld %ld\n\n", max, nr);
*/
level * b = (level *) calloc (nr, sizeof(level));
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;
j++;
l = a[i].l;
}
//for (i=0; i<nr; i++)
//printf("*%ld %ld\n", b[i].l, b[i].poz);
long *heap = (long *) calloc(max, sizeof(long));
//heap[0] = a[0].g
//make_heap(heap, heap+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++)
{
//printf("---%ld\n",heap[i]);
g+= (-heap[i]);
}
fprintf(ff,"%ld",g);
fclose(f);
fclose(ff);
return 0;
}