Pagini recente » Cod sursa (job #1250422) | Cod sursa (job #627064) | Cod sursa (job #2703290) | Cod sursa (job #2231549) | Cod sursa (job #435205)
Cod sursa(job #435205)
#include<iostream>
//#include<fstream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include<vector>
using namespace std;
/******************************************************************************
* *
* minim() - determina elementul minim dintr-un vector *
* *
******************************************************************************/
int minim(vector<int> v, int n){
int i;
int min = v[0];
for(i = 1; i<n; i++)
if(min > v[i])
min = v[i];
return min;
}
/******************************************************************************
* *
* index() - determinarea pozitiei unui element intr-un vector *
* *
******************************************************************************/
int index(int x, vector<int> v, int n){
int i;
for(i = 0; i<n; i++)
if(x == v[i])
return i;
return -1;
}
/******************************************************************************
* *
* suma() - determinarea sumei elementelor dintr-un vector *
* *
******************************************************************************/
int suma(vector<int> v, int n){
int i, s = 0;
for(i = 0; i<n; i++)
s += v[i];
return s;
}
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());
// printf("%d\n",gutui.front().first);
for(i = 0; i<n; i ++)
/* 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());
/* 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){
replace(cules.begin(),cules.end(),cules.front(),gutui[i]);
}
}
//for(i=0; i<n; i++)
// printf("%d %d\n",cules[i].first,cules[i].second);
i = 0;
int s = 0;
int len = cules.size();
for(i=0; i<len; i++)
s += cules[i].second;
fprintf(g,"%d\n",s);
fclose(f);
fclose(g);
return 0;
}