Cod sursa(job #3148228)

Utilizator RosheRadutu Robert Roshe Data 29 august 2023 22:49:13
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <utility>
#include <algorithm>
#include <iomanip>
#include <fstream>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");

pair <float, int> p[1000];

int main(){
  int n, gmax, g, v;
  in >> n >> gmax;
  for(int i = 0; i<n; i++){
    in >> g >> v;
    float ratio = (float)v / g;
    p[i].first = ratio;
    p[i].second = g;
  }
  sort(p, p + n, greater<pair<float,int> >());
  //for(int i = 0; i<n ;i++)
    //cout << p[i].first << " "<< p[i].second << endl;
  int ans = 0;
  for(int i = 0; i<n; i++){
    if(gmax - p[i].second >= 0){
      ans = ans + p[i].second * p[i].first;
      gmax = gmax - p[i].second;
    }
    else {
      ans = ans + (float)(gmax )* p[i].first;
      break;
    }
    if(gmax == 0)
      break;
  }
   out << ans;
}