Pagini recente » Cod sursa (job #275973) | Cod sursa (job #3221693) | Cod sursa (job #2560109) | Cod sursa (job #2576339) | Cod sursa (job #2065511)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("ruscac.in");
ofstream g ("rucsac.out");
int n,Gm;
double prM;
struct nod
{
int gr;
int val;
double pr;
} a[1005];
bool cmp (nod x, nod y)
{
if(x.pr>y.pr) return true;
else
return false;
}
void load ()
{
f>>n>>Gm;
for( int i=1; i<=n; i++ )
{
f>>a[i].gr>>a[i].val;
a[i].pr=(double)a[i].val/a[i].gr;
}
}
int main ()
{
int k=0,nr=0;
load ();
sort (a+1,a+n+1,cmp);
for(int i=1; i<=n; i++)
{
if(a[i].gr+k<=Gm)
{
prM+=a[i].val;
k+=a[i].gr;
}
else if(a[i].gr+k>Gm)
{
nr=Gm-k;
prM+=nr*a[i].pr;
break;
}
}
g<<(int)prM;
return 0;
}