Cod sursa(job #2585223)
| Utilizator | Data | 18 martie 2020 20:07:24 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.58 kb |
#include <cstdio>
#include <algorithm>
using namespace std;
struct item
{
int g,p;
}v[1005];
bool cmp(item a,item b)
{
return a.p*b.g>b.p*a.g;
}
int main()
{
int n,g,s,gs,i;
scanf("%d%d",&n,&g);
for (i=1;i<=n;i++)
{
scanf("%d%d",&v[i].g,&v[i].p);
}
sort(v+1,v+n+1,cmp);
gs=0;
s=0;
for (i=1;i<=n && gs + v[i].g <= g;i++)
{
s=s+v[i].p;
gs=gs+v[i].g;
}
if(i <= n)
printf("%f",(float)((float)s+(float)(g - gs)/v[i].g*v[i].p));
else printf("%d", s);
return 0;
}
