Cod sursa(job #2971115)

Utilizator 222cezarCezar Stilpeanu 222cezar Data 26 ianuarie 2023 17:28:39
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse4")
using namespace std;

const int NMAX = 5002;
struct obiect
{
  int g;
  int p;
  int ef;
} o[NMAX];

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

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(0);

  cin >> n >> gmax;
  for(int i = 1; i <= n; i++)
  {
    cin >> o[i].g >> o[i].p;
    o[i].ef = o[i].p / o[i].g;
  }
  cin.close();

  sort(o + 1, o + n + 1, [&](obiect a, obiect b) {return a.ef > b.ef; });
  int i = 1;
  int pf = 0;
  while(i <= n && gmax >= 0)
  {
    if(o[i].g <= gmax)
    {
      pf += o[i].p;
    }
    else
    {
      pf += gmax * o[i].ef;
    }
    gmax -= o[i].g;
    i++;
  }

  cout << fixed << setprecision(6) << pf;
  cout.close();
  return 0;
}