Pagini recente » Cod sursa (job #292754) | Cod sursa (job #368733) | Cod sursa (job #389988) | Cod sursa (job #427896) | Cod sursa (job #2509666)
#include <bits/stdc++.h>
using namespace std;
struct obj{
int g, c;
double r = 0.0;
}a[5001];
bool cmp(obj a, obj b){
return a.r > b.r;
}
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main(){
int n, w;
fin >> n >> w;
for (int i = 0; i < n; i++){
fin >> a[i].g >> a[i].c;
a[i].r = (double)a[i].c/a[i].g;
}
sort(a, a+n, cmp);
int greutate_curenta = 0;
int s = 0;
for (int i = 0; i < n; i++){
if (greutate_curenta + a[i].g <= w){
greutate_curenta += a[i].g;
s += a[i].c;
}
else {
int ok = w - greutate_curenta;
s += a[i].c*((double)ok/a[i].g);
break;
}
}
fout << s << endl;
}