Cod sursa(job #2525004)

Utilizator danalex032003Dan Alexandru danalex032003 Data 16 ianuarie 2020 18:05:38
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
#define nmax 100005

using namespace std;

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

struct s {
    double greutate, profit, raport;
    int indice;
};

s v[nmax];
int n, g;

void input()
{
    fin >> n >> g;
    for (int i = 1; i <= n; i++)
    {
        fin >> v[i].greutate >> v[i].profit;
        v[i].raport = v[i].profit / v[i].greutate;
        v[i].indice = i;
    }
}

bool sortareRaport (s left, s right)
{
    return (left.raport > right.raport);
}

int greedy()
{
    int i = 1;
    int sum = v[i].profit;
    int verif = v[i].greutate;
    while (verif <= g)
    {
        i++;
        if (verif + v[i].greutate <= g)
        {
            verif += v[i].greutate;
            sum += v[i].profit;
        }
        else break;
    }
    if (verif != g && v[i].indice)
    {
        sum += v[i].profit / (v[i].greutate / (g - verif));
    }
    return sum;
}

int main()
{
    input();
    sort(v + 1, v + n + 1, sortareRaport);
    fout << greedy();
    return 0;
}