Pagini recente » Cod sursa (job #420374) | Cod sursa (job #3132576) | Cod sursa (job #398695) | hehe | Cod sursa (job #435222)
Cod sursa(job #435222)
#include<iostream>
//#include<fstream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include<vector>
using namespace std;
bool sortW(pair<int,int>x,pair<int,int>y) {
return(x.second > y.second);
}
bool sortH(pair<int,int>x, pair<int, int>y) {
return(x.first > y.first);
}
int main(){
int n; // nr de gut
int h; // inaltimea maxima
int prag; // inaltimea cu care se inalta ramurile
int pr = 0; // inaltimea curenta cu care se inalta ramurile
vector< pair<int,int> > gutui;
vector< pair<int,int> > cules; // greutatea fiecarei gut culese
pair<int,int> k ; // lungimea vectorului cules[]
int i; // variabile auxiliare
FILE *f, *g;
f = fopen("gutui.in","r");
g = fopen ("gutui.out","w");
int x,y;
/* citire date de 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());
int len = gutui.size();
for(i = 0; i<len; i ++){//printf("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());
//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){
//printf("schimb %d\n",cules.front().second);
//replace(cules.begin(),cules.end(),cules.front(),gutui[i]);
//sort(cules.begin(),cules.end(), sortW);
pop_heap(cules.begin(), cules.end());
cules.pop_back();
cules.push_back(gutui[i]);
push_heap(cules.begin(),cules.end());
}
}
}
len = cules.size();
///for(i=0; i<len; i++)
// printf("%d %d\n",cules[i].first,cules[i].second);
int s = 0;
for(i=0; i<len; i++)
s += cules[i].second;
fprintf(g,"%d\n",s);
fclose(f);
fclose(g);
return 0;
}