Cod sursa(job #2585223)

Utilizator PetrescuAlexandru Petrescu Petrescu 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;
}