Cod sursa(job #2930232)

Utilizator RaresIGIIgescu Rares RaresIGI Data 27 octombrie 2022 19:30:04
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#define N 100005
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n,GM;
double s=0;

struct mutare
{
    int gre,val;
    double rap;

} a[N];

void Citire()
{
    int i;
    fin>>n>>GM;
    for(i=1;i<=n;i++)
        {
            fin>>a[i].gre>>a[i].val;
            a[i].rap=a[i].val/a[i].gre;
        }
}

void Sortare()
{
    bool ok=0;
    mutare aux;
    int i;
    while(ok==0)
    {
        ok=1;
        for(i=1;i<n;i++)
            if(a[i].rap<a[i+1].rap)
        {
            aux=a[i];
            a[i]=a[i+1];
            a[i+1]=aux;
            ok=0;
        }
    }
}

void rezolva()
{
    int i;
    for(i=1;i<=n && GM>0;i++)
        if(a[i].gre<=GM)
        {
            GM=GM-a[i].gre;
            s=s+a[i].val;
        }
        else
        {
            s=s+GM*a[i].rap;
            GM=0;
        }
    fout<<s;
}

int main()
{
    Citire();
    Sortare();
    rezolva();
    return 0;
}