Pagini recente » Diferente pentru preoni-2006/runda-2/solutii intre reviziile 17 si 16 | Cod sursa (job #3037818) | Istoria paginii utilizator/spatiisaudiacritice | Cod sursa (job #2012661) | Cod sursa (job #2686031)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
struct ceva
{
int greu,val;
}v[1005];
int n,i,gmax,g;
double q,x;
bool comp(ceva a, ceva b)
{
return a.val*b.greu>a.greu*b.val;
}
int main()
{
fin>>n>>gmax;
for(i=1;i<=n;i++)
fin>>v[i].greu>>v[i].val;
sort(v+1,v+n+1,comp);
i=1;
while(i<=n)
{
if(g+v[i].greu<=gmax)
{
g=g+v[i].greu;
q=q+v[i].val;
i++;
}
else
if(gmax-g>0)
{
x=1.0*(gmax-g)/v[i].greu;
g=gmax;
q=q+x*v[i].val;
i++;
}
else
i=n+1;
}
fout<<(int)q;
return 0;
}