Pagini recente » Cod sursa (job #40948) | Cod sursa (job #1773525) | Cod sursa (job #2205619) | Cod sursa (job #2018812) | Cod sursa (job #1844744)
#include <bits/stdc++.h>
using namespace std;
int n,gmax,i,s,in,x[5005];
double c[5005];
bool ok;
struct nod
{
double cost;
int ind;
}c1[5005],aux;
int main()
{
ifstream f("rucsac.in");
ofstream g("rucsac.out");
f>>n>>gmax;
for(i=1;i<=n;i++)
{
f>>x[i]>>c[i];
c1[i].cost=c[i]/x[i];
c1[i].ind=x[i];
}
do
{
ok=true;
for(i=1;i<n;i++)
if(c1[i].cost<c1[i+1].cost)
{aux=c1[i];c1[i]=c1[i+1];c1[i+1]=aux;ok=false;}
}while(!ok);
for(i=1;i<=n;i++)
if(in+c1[i].ind<gmax ) {in+=c1[i].ind; s+=c1[i].ind*c1[i].cost;}
else s+= c1[i].cost*(gmax-in),in=gmax;
g<<s;
return 0;
}