Pagini recente » Cod sursa (job #2104207) | Cod sursa (job #13109) | Cod sursa (job #264030) | Cod sursa (job #2468593) | Cod sursa (job #1579799)
#include <algorithm>
#include <stdio.h>
#include <cmath>
using namespace std;
FILE*f=fopen("rucsac.in","r");
FILE*h=fopen("rucsac.out","w");
struct ob
{
int c,g;
int o;
}a[50001];
int n;
int gm,ct;
int comp(ob a,ob b)
{
if (fabs((float)a.c/a.g-(float)b.c/b.g)<0.0001) return a.g<b.g;
else return (float)a.c/a.g-(float)b.c/b.g>0.0001;
}
void citire()
{
int i;
fscanf(f,"%d%d",&n,&gm);
for (i=1;i<=n;i++) fscanf(f,"%d%d",&a[i].g,&a[i].c);
}
int main()
{
int i;
citire();
sort(a+1,a+n+1,comp);
ct=0;
i=1;
while (gm>0&&i<=n)
{
if (a[i].g<gm)
{
gm-=a[i].g;
ct+=a[i].c;
}
else
{
if (a[i].g==gm)
{
ct+=a[i].c;
gm=0;
}
}
i++;
}
fprintf(h,"%d",ct);
return 0;
}