Pagini recente » Cod sursa (job #2774151) | Cod sursa (job #1642592) | Cod sursa (job #2589016) | Cod sursa (job #2851581) | Cod sursa (job #438362)
Cod sursa(job #438362)
Utilizator |
Catalin nc3b |
Data |
10 aprilie 2010 18:17:04 |
Problema |
Gutui |
Scor |
100 |
Compilator |
cpp |
Status |
done |
Runda |
teme_upb |
Marime |
1.54 kb |
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
struct gutuie {
int height;
int weight;
};
bool compare_gutui(gutuie g1, gutuie g2)
{
return(g1.weight > g2.weight);
}
int main()
{
ifstream fin;
ofstream fout;
fin.open("gutui.in", ios::in);
fout.open("gutui.out", ios::out);
if( !fin.is_open() || !fout.is_open() )
{
cerr << "Unul din fisiere nu a putut fi deschis \n";
return(1);
}
int N = 0;
int H = 0;
int U = 0;
fin >> N;
fin >> H;
fin >> U;
// cout << N << " " << H << " " << U << endl;
list <gutuie> gutui;
int current_height = H;
for(int i = 0; i < N; i ++)
{
gutuie g;
fin >> g.height;
fin >> g.weight;
gutui.push_back(g);
}
gutui.sort(compare_gutui);
char * result = new char[N];
memset(result, 0, N);
int credit = 0;
int gweight = 0;
for(list <gutuie>::iterator it = gutui.begin();
(it != gutui.end()) && 0 != current_height;
it ++)
{
credit = (current_height - (*it).height) / U;
// cout << (*it).height << " : " << (*it).weight << " credit: " << credit << endl;
if(credit < 0)
{
continue;
}
credit = min (credit, N - 1);
for(int i = credit; i>= 0; i --)
{
if(0 == result[i])
{
//nu e nici o gutuie pe pozitia aia
//culegem gutuia noastra
result[i] = 1;
gweight += (*it).weight;
break; //este esential
}
}
}
fout << gweight;
fin.close();
fout.close();
return(0);
}