Cod sursa(job #2685295)

Utilizator Florian11232Florian Susai Florian11232 Data 16 decembrie 2020 15:19:29
Problema Problema rucsacului Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#define dim  6000005
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
struct rucsac
{
    int greutate;
    int profit;
};
rucsac elem[10001];

bool cmp(rucsac e1, rucsac e2) {
    return e1.profit/e1.greutate > e2.profit/e2.greutate;
}

int main()
{
  

    int numar,capacitate,i;
    
    in>>numar>>capacitate;
    
    for(i=0;i<numar;i++)
    {
        in>>elem[i].greutate>>elem[i].profit;
    }

    sort(elem, elem + numar, cmp);

    /*for (i = 0; i < numar; i++) {
        out << elem[i].greutate << " " << elem[i].profit << '\n';
    }*/
    int maxi=0, idx = 0;
    int rezultat=0; 
    while(capacitate != maxi)
    {
        if (elem[idx].greutate + maxi <= capacitate) {
            // iau tot obiectul
            rezultat += elem[idx].profit;
            maxi += elem[idx].greutate;
        } else {
            // trebuie sa iau o fractiune din obiectul curent
            rezultat += (capacitate - maxi) * elem[idx].profit/elem[idx].greutate; 
            maxi = capacitate;
        }
        idx++;
        // cout << rezultat << "\n";
    }

    out<<rezultat;
    
    return 0;
}