Pagini recente » Autentificare | Cod sursa (job #1314944) | Cod sursa (job #2486544) | Cod sursa (job #1983353) | Cod sursa (job #1707890)
#include <fstream>
#include<algorithm>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
struct piatra{
int val,greu,ind;
};
piatra A[100100];
int N,M;
double Gr,rs;
bool comp(piatra a,piatra b){
return 1.0*a.val/a.greu > 1.0*b.val/b.greu;
}
void greedy()
{ int i;
for (i=0,Gr=M;i<N && Gr;++i){
fo << A[i].ind << ' ';
if(Gr >= A[i].greu){
Gr-=A[i].greu;
rs+=A[i].val;
fo << 100 << '\n';
}
else{
rs+=1.0*Gr*(1.0*A[i].val/A[i].greu);
fo << (100.0*Gr/A[i].greu);
Gr = 0;
}
}
}
int main()
{
int i;
fi>>N>>M;
for (i=0;i<N;++i)
{
fi>>A[i].val >> A[i].greu;
A[i].ind = i+1;
}
sort(A,A+N,comp);
greedy();
fo << '\n' << rs;
return 0;
}