Cod sursa(job #2971144)

Utilizator RORO123bBarbulescu Robert RORO123b Data 26 ianuarie 2023 18:52:27
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

struct obj{
double v,g,m;
}v[1001];

int n,gmax,gt;
int sol;

bool compare(obj a, obj b)
{
    return a.m>b.m;
}

int main()
{
    cin>>n>>gmax;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].g>>v[i].v;
        v[i].m=v[i].v/v[i].g;
    }
    sort(v+1,v+1+n,compare);
    for(int i=1;i<=n;i++)
    {
        if(v[i].g+gt<=gmax)
            {
                gt+=v[i].g;
                sol+=v[i].v;
            }
        else
        {
            sol+=(v[i].m*(gmax-gt));
            gt=gmax;
            break;
        }
    }
    cout<<sol;
    return 0;
}