Pagini recente » Cod sursa (job #17806) | Cod sursa (job #2180563) | Cod sursa (job #1266490) | Cod sursa (job #1522526) | Cod sursa (job #435485)
Cod sursa(job #435485)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
bool sortW(pair<unsigned int,unsigned int>x,pair<unsigned int,unsigned int>y) {
return(x.second > y.second);
}
bool sortH(pair<unsigned int,unsigned int>x, pair<unsigned int, unsigned int>y) {
return(x.first > y.first);
}
int main(){
unsigned int n; // nr de gut
unsigned int h; // inaltimea maxima
unsigned int prag; // inaltimea cu care se inalta ramurile
unsigned int pr = 0; // inaltimea curenta cu care se inalta ramurile
vector< pair<unsigned int,unsigned int> > gutui;
vector< pair<unsigned int,unsigned int> > cules; // greutatea fiecarei gut culese
pair<unsigned int,unsigned int> k ; // lungimea vectorului cules[]
unsigned int i; // variabile auxiliare
FILE *f, *g;
f = fopen("gutui.in","r");
g = fopen ("gutui.out","w");
unsigned int x,y;
/* citire date de unsigned intrare */
fscanf(f,"%d %d %d", &n, &h, &prag);
gutui.resize(n);
for(i = 0; i<n; i++){
fscanf(f, "%d %d",&x,&y);
gutui[i] = make_pair(x,y);
}
sort(gutui.begin(), gutui.end(), sortH);
pr = 0;
make_heap(cules.begin(),cules.end());
unsigned int len = gutui.size();
for(i = 0; i<len; i ++){//prunsigned intf("bag %d\n",gutui[i].second);
/* verificare daca Gigel poate ajunge la ramuri */
if((gutui[i].first + pr) <= h && pr <= h){
cules.push_back(gutui[i]);
push_heap(cules.begin(),cules.end(),sortW);
// printf("bag %d\n",gutui[i].second);
/* cresterea inaltimii cu care se ridica ramurile */
pr +=prag;
}
else{
/* verificare daca nu a fost aleasa o greutate mai
* usoara decat cea curenta */
if(cules.front().second < gutui[i].second){
pop_heap(cules.begin(), cules.end(),sortW);
cules.pop_back();
cules.push_back(gutui[i]);
push_heap(cules.begin(),cules.end(),sortW);
}
}
}
len = cules.size();
///for(i=0; i<len; i++)
// prunsigned intf("%d %d\n",cules[i].first,cules[i].second);
unsigned int s = 0;
for(i=0; i<len; i++)
s += cules[i].second;
fprintf(g,"%d\n",s);
fclose(f);
fclose(g);
return 0;
}