Cod sursa(job #1973379)

Utilizator AlexDontuAlex Dontu AlexDontu Data 24 aprilie 2017 21:08:23
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
struct  stec
{
    long x,y;
} v[8001];
long long n,i,s=0;
float b,gmax;
long long a[8001];
long long compare (stec a, stec b)
{float t,p;
 t=(float)a.y/a.x;
 p=(float)b.y/b.x;
    return (t<p||(t==p&&a.x<=b.x));
}
int main()
{
    fin>>n>>gmax;
    for (i=1;i<=n;i++) {fin>>v[i].x>>v[i].y;}
    sort (v+1,v+n+1,compare);
    for (i=n;i>=1;i--) {if (v[i].x<=gmax) {gmax=gmax-v[i].x;
                                           s=s+v[i].y;}
                        else if (v[i].x>gmax) {b=v[i].x/gmax;
                                               s=s+v[i].y/b;break;}
                        }
    fout<<s;
    return 0;
}