Pagini recente » Cod sursa (job #903973) | Cod sursa (job #1733419) | Cod sursa (job #1137048) | Cod sursa (job #1644019) | Cod sursa (job #441633)
Cod sursa(job #441633)
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
const long int NMAX = 100005;
const long int 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_level (gutuie i, gutuie j)
{
return i.level > j.level;
}
bool cmp_weight (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_level );
make_heap (H.begin(), H.end(), cmp_weight );
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(), cmp_weight);
H.pop_back();
}
cur_level = V[i].level;
}
H.push_back (V[i]);
push_heap (H.begin(), H.end(), cmp_weight);
}
while ( cur_level-- > 0 && H.size() )
{
Gmax += H.front().w;
pop_heap( H.begin(), H.end(), cmp_weight);
H.pop_back();
}
printf ("%ld\n", Gmax);
return 0;
}