Pagini recente » Cod sursa (job #1990389) | Cod sursa (job #1332640) | Cod sursa (job #2833932) | Cod sursa (job #2055539) | Cod sursa (job #438639)
Cod sursa(job #438639)
#include <stdio.h>
#include <malloc.h>
#include <algorithm>
#include <vector>
using namespace std;
#define u_int unsigned int
bool desc(u_int *u, u_int *d){
return u[0]>d[0];
}
int main(){
FILE *f, *g;
f = fopen ("gutui.in", "r");
g = fopen ("gutui.out", "w");
u_int H, U, **a, cules = 0, h_mom;
int N, i, n, p = 0;
vector<u_int> momentan;
vector<u_int>::iterator it;
fscanf(f, "%d %u %u", &N, &H, &U);
n = N;
a = (u_int**)malloc(N*sizeof(u_int*));
for(i = 0; i < N; i ++){
a[i] = (u_int*)malloc(2*sizeof(u_int));
fscanf(f, "%u %u", &a[i][0], &a[i][1]);
}
//sort descrescator
sort(a, a+N, desc);
//pornesc de la ultimul nivel, cel mai jos
if(H%U == 0)
h_mom = U;
else
h_mom = H - ((H / U) * U);
//incep sa "culeg" gutui, pornind de la ultimul nivel
while((h_mom <= H) && (N > 0 || momentan.size() > 0)){
if(momentan.size() > 0){
cules = cules + momentan.front();
pop_heap(momentan.begin(), momentan.end());
momentan.pop_back();
h_mom = h_mom + U;
}
else
if(p)
h_mom = h_mom + U;
p = 1;
//parcurge un nivel
while(N > 0){
//s-a terminat nivelul -> iese din while
if(a[N-1][0] > h_mom)
break;
//pune gutuile de pe nivel in momentan
momentan.push_back(a[N-1][1]);
N --;
push_heap(momentan.begin(), momentan.end());
}
}
for(i = 0; i < n; i ++)
free(a[i]);
free(a);
fprintf(g, "%u", cules);
return 0;
}