Pagini recente » Cod sursa (job #208019) | Cod sursa (job #1828381) | Cod sursa (job #1620918) | Cod sursa (job #370752) | Cod sursa (job #441857)
Cod sursa(job #441857)
/*
* @ Copyright, 2010
* Mihai Tabara
* 325 CA
* Task - Homework 1 ( Algorithm Design )
* Time Complexity - O(N log N)
* Memory Complexity - O ( N + DIM ) where DIM represents maximum number of characters in the input ( parsing the reading )
* Solving Method - Dynamic Programming Behaviour implemented as Greedy Algorithm
* Language used: C++
* Program: gutui
*/
#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];
/* Parsing the input reading */
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);
}
/* Descending sorting of the quinces based on their level */
sort ( V.begin(), V.end(), cmp_level );
/* Building the heap */
make_heap (H.begin(), H.end(), cmp_weight );
cur_level = V[0].level;
/* Cycling through every quince */
for (i = 0; i < N; ++i) {
if (V[i].level != cur_level) { /* Level changing */
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]); /* Otherwise, building the heap */
push_heap (H.begin(), H.end(), cmp_weight);
}
/* In case there are still possible moves to make */
while ( cur_level-- && H.size() )
{
Gmax += H.front().w;
pop_heap( H.begin(), H.end(), cmp_weight);
H.pop_back();
}
printf ("%ld\n", Gmax);
return 0;
}