Pagini recente » Cod sursa (job #2750895) | Cod sursa (job #21434) | Cod sursa (job #540426) | Cod sursa (job #943441) | Cod sursa (job #441616)
Cod sursa(job #441616)
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 100005
#define DIM 1500099
const char* in = "gutui.in";
const char* out = "gutui.out";
typedef struct {
long int w;
long int h;
long int level;
} gutuie;
long int N, Hmax, U, Gmax;
vector<gutuie> V, H;
bool cmp (gutuie i, gutuie j) {
return (i.level > j.level);
}
bool cmp2 (gutuie i, gutuie j){
return (i.w < j.w);
}
int main(void)
{
freopen ( in, "r", stdin );
freopen ( out, "w", stdout );
long int poz = 0, i, height, weight, cur_level, K;
gutuie tmp;
char buf[DIM];
fread (buf, 1, DIM, stdin);
#define cit(x) \
{ \
x = 0; \
while (buf[poz] < '0') \
{ \
++poz; \
if (poz == DIM) { \
fread (buf, 1, DIM, stdin); poz = 0; } \
} \
while (buf[poz] >= '0') \
{ \
x = x*10 + buf[poz] - '0'; \
if (++poz == DIM) { \
fread (buf, 1, DIM, stdin); poz = 0; } \
} \
}
cit(N) cit(Hmax) cit(U)
for (i = 0; i < N; ++i)
{
cit(height) cit(weight)
tmp.h = height;
tmp.w = weight;
tmp.level = (Hmax - height)/U + 1;
V.push_back (tmp);
}
sort ( V.begin(), V.end(), cmp );
make_heap (H.begin(), H.end(), cmp2);
cur_level = V[0].level;
for (i = 0; i < N; ++i)
{
if (V[i].level != cur_level)
{
for (K = cur_level; K > V[i].level && H.size(); --K)
{
Gmax += H.front().w;
pop_heap(H.begin(), H.end(), cmp2);
H.pop_back();
}
cur_level = V[i].level;
}
H.push_back (V[i]);
push_heap (H.begin(), H.end(), cmp2);
}
for (K = cur_level; K > 0 && H.size(); --K)
{
Gmax += H.front().w;
pop_heap( H.begin(), H.end(), cmp2);
H.pop_back();
}
printf ("%ld\n", Gmax);
return 0;
}