Pagini recente » Cod sursa (job #1137789) | Cod sursa (job #2399212) | Cod sursa (job #3004461) | Cod sursa (job #3031662) | Cod sursa (job #2971115)
#include <fstream>
#include <algorithm>
#include <iomanip>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse4")
using namespace std;
const int NMAX = 5002;
struct obiect
{
int g;
int p;
int ef;
} o[NMAX];
int n; int gmax;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
signed main()
{
cin.tie(0);
ios::sync_with_stdio(0);
cin >> n >> gmax;
for(int i = 1; i <= n; i++)
{
cin >> o[i].g >> o[i].p;
o[i].ef = o[i].p / o[i].g;
}
cin.close();
sort(o + 1, o + n + 1, [&](obiect a, obiect b) {return a.ef > b.ef; });
int i = 1;
int pf = 0;
while(i <= n && gmax >= 0)
{
if(o[i].g <= gmax)
{
pf += o[i].p;
}
else
{
pf += gmax * o[i].ef;
}
gmax -= o[i].g;
i++;
}
cout << fixed << setprecision(6) << pf;
cout.close();
return 0;
}