Pagini recente » infoarena - te ajutam sa devii olimpic! | Cod sursa (job #919821) | Cod sursa (job #3164063) | Cod sursa (job #212674) | Cod sursa (job #2773276)
#include <fstream>
#include <algorithm>
#include <cmath>
struct obiect{
int greutate, valoare;
};
int n, Gmax;
obiect O[5001];
std::ifstream fin("rucsac.in");
std::ofstream fout("rucsac.out");
bool fcmp(obiect A, obiect B)
{
return A.valoare * B.greutate > A.greutate * B.valoare;
}
int main(){
fin >> n >> Gmax;
for(int i=1 ; i<=n ; ++i)
fin >> O[i].greutate >> O[i].valoare;
std::sort(O + 1 , O + n + 1, fcmp);
int G = 0;
double V = 0;
int i = 1;
while( i <= n)
{
if(G + O[i].greutate <= Gmax)
{
G += O[i].greutate;
V += O[i].valoare;
i ++;
}
else
if(Gmax - G > 0)
{
int x = Gmax - G;
double factor = 1.0 * x / O[i].greutate;
G = Gmax;
V += factor * O[i].valoare;
i++;
}
else
i = n + 1;
}
fout << floor(V);
return 0;
}