Cod sursa(job #2971182)

Utilizator SergetecLefter Sergiu Sergetec Data 26 ianuarie 2023 19:38:39
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
/*
  Lefter Sergiu - 26/01/2023
*/
#include <fstream>
#include <algorithm>

using namespace std;

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

struct obiect {
    int g, v;
    int p;
};

obiect a[1000001];
int n, G;

int cmp(obiect x, obiect y) {
    return x.p > y.p;
}

int main() {
    in >> n >> G;
    for (int i = 1; i <= n; ++i) {
        in >> a[i].g >> a[i].v;
        a[i].p = a[i].v / a[i].g;
    }
    sort(a + 1, a + n + 1, cmp);
    float val = 0;
    for (int i = 1; i <= n && G >= 0; ++i) {
        if (a[i].g <= G) {
            G -= a[i].g;
            val += a[i].v;
        }
        else {
            val = val + G * a[i].p;
            G = 0;
        }
    }
    out << val;
    in.close();
    out.close();
    return 0;
}