Pagini recente » Cod sursa (job #2977076) | Cod sursa (job #2899478) | Cod sursa (job #1267320) | Cod sursa (job #2900445) | Cod sursa (job #437817)
Cod sursa(job #437817)
# include <iostream>
# include <fstream>
# include <cstdlib>
# define MAXN 100000
typedef struct GUTUIE{
long int h,w,tic;
} GUTUIE;
int comparaGutui(const void *aa, const void *bb)
{
GUTUIE* a = (GUTUIE*) aa;
GUTUIE* b = (GUTUIE*) bb;
if (a->tic < b->tic) return -1;
if (a->tic > b->tic) return 1;
if (a->w > b->w ) return 1;
if (a->w < b->w ) return -1;
return 0;
}
GUTUIE gutui[MAXN+1];
long int n,u,h;
//acesta este un MIN-HEAP (contine in varf mereu INDEXUL la cea mai usoara gutuie)
class HEAP{
private:
long int v[MAXN+1];
long int len;
void surface(long int i){
long int aux;
while (i/2 && gutui[v[i]].w < gutui[v[i/2]].w){
aux = v[i]; v[i] = v[i/2]; v[i/2] = aux;
i/=2;
}
}
void submerge(long int i){
long int aux,min;
do{
min = i;
if (2*i <= len && gutui[v[2*i ]].w < gutui[v[min]].w) min = 2*i;
if (2*i+1<= len && gutui[v[2*i+1]].w < gutui[v[min]].w) min = 2*i+1;
if (i==min) break;
aux = v[i]; v[i] = v[min]; v[min] = aux;
i = min;
} while (1);
}
public:
HEAP(){
len = 0;
}
void insert(long int i){
v[++len] = i;
surface(len);
}
long int topWeight(){
return gutui[v[1]].w;
}
long int extract(){
long int sol = v[1];
v[1] = v[len];
len --;
submerge(1);
return sol;
}
long int totalSum(){
long int i, sol = 0;
for (i=1;i<=len;i++)
sol += gutui[v[i]].w;
return sol;
}
};
void citire()
{
std::ifstream f("gutui.in",std::ios::in);
f >> n;
f >> h;
f >> u;
long int i;
for (i=1;i<=n;i++){
f >> gutui[i].h;
f >> gutui[i].w;
gutui[i].tic = (h-gutui[i].h)/u + 1;
//nu ne intereseaza gutuile care sunt peste inaltimea h
if (gutui[i].h > h){
i--;
n--;
}
}
f.close();
qsort(gutui+1,n,sizeof(GUTUIE),comparaGutui);
}
void scrie(long int sol)
{
std::ofstream g("gutui.out",std::ios::out | std::ios::trunc);
g << sol << "\n";
g.close();
}
void calculeaza()
{
HEAP h;
long int i,lasttic = 0;
//iteram prin toate gutuile. Retinem mereu la ce "tic" suntem :D
for (i=1;i<=n;i++){
//daca poti sa o culegi linistit
if (gutui[i].tic > lasttic){
h.insert(i);
lasttic++;
} else if (h.topWeight() < gutui[i].w){ //ai optiunea sa o inlocuiesti cu una pe care deja ai cules'o
h.extract();
h.insert(i);
}
}
scrie(h.totalSum());
}
int main()
{
citire();
calculeaza();
return 0;
}