Cod sursa(job #2051779)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 29 octombrie 2017 15:36:23
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,gmax;
float cmax;
struct ob {
    int o,g;
    float c;
}v[1015];

int comp(ob x,ob y) {
    return x.c/x.g>y.c/y.g;
}

void sol() {
    int i;
    float p;
    for (i=1;i<=n && gmax!=0;i++)
        if (v[i].g<=gmax) {
            gmax-=v[i].g;
            cmax+=v[i].c;
            //cout<<v[i].o<<' '<<1<<'\n';
        }
        else {
            p=(float)gmax/v[i].g;
            gmax=0;
            cmax+=v[i].c*p;
            //cout<<v[i].o<<' '<<v[i].c*p<<'\n';;
        }
    g<<(int)cmax;
}

int main() {
    int i;
    f>>n>>gmax;
    for (i=1;i<=n;i++) {
        f>>v[i].g>>v[i].c;
        v[i].o=i;
    }
    sort(v+1,v+n+1,comp);
    //cout<<'\n';
    /*for (i=1;i<=n;i++)
        cout<<v[i].g<<' '<<v[i].c<<'\n';
    */sol();
    return 0;
}