Pagini recente » Cod sursa (job #1218754) | Cod sursa (job #1075959) | Cod sursa (job #1386161) | Cod sursa (job #2422460) | Cod sursa (job #441667)
Cod sursa(job #441667)
#include<fstream>
#include<cstdlib>
#include<climits>
#include<vector>
#include<algorithm>
#define IN "gutui.in"
#define OUT "gutui.out"
using namespace std;
typedef struct
{
int h;
int w;
int l;
} GUTUIE;
bool cmph ( GUTUIE i, GUTUIE j)
{
return i.h > j.h;
}
bool cmpw ( GUTUIE i, GUTUIE j)
{
return i.w < j.w;
}
int main (int argc, char **argv)
{
FILE *fin = fopen (IN, "r");
FILE *fout = fopen (OUT, "w");
int i;
int N, H, U;
long G = 0;
fscanf (fin, "%d%d%d", &N, &H, &U);
vector <GUTUIE> g, Heap;
make_heap (Heap.begin(), Heap.end(), cmpw);
GUTUIE a;
for (i = 0; i < N; ++i)
{
fscanf(fin, "%d%d", &a.h, &a.w);
a.l = a.h/U + 1;
g.push_back(a);
}
sort (g.begin(), g.end(), cmph);
/*for ( i = 0; i < N ;++i)
printf("Gutuie :\tinaltime: %d\t greutate: %d\t level: %d\n", g[i].h, g[i].w, g[i].l);
printf("\n");*/
int current = g[N-1].l;
Heap.push_back (g[N-1]);
push_heap (Heap.begin(), Heap.end(), cmpw);
for (i = N-2; i >= 0; --i)
{
if (g[i].l > g[i+1].l)
{
for (; current < g[i].l && Heap.size() ; ++current)
{
G += Heap.front().w;
pop_heap (Heap.begin(), Heap.end(), cmpw);
Heap.pop_back();
}
}
Heap.push_back (g[i]);
push_heap (Heap.begin(), Heap.end(), cmpw);
}
// Daca mai raman gutui de cules
for ( ; current < H/U+1 && Heap.size() ; ++current)
{
G += Heap.front().w;
pop_heap (Heap.begin(), Heap.end(), cmpw);
Heap.pop_back();
}
/*for (i = 0 ; i < Heap.size(); ++i)
fprintf (fout, "GUTUIE %d %d\n", Heap[i].w, Heap[i].h);
fprintf (fout, "\n");*/
fprintf (fout, "%ld\n", G);
fclose (fin);
fclose (fout);
return 0;
}