Cod sursa(job #2509201)

Utilizator lflorin29Florin Laiu lflorin29 Data 13 decembrie 2019 22:30:03
Problema Problema rucsacului Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>

using namespace std;


int main() {
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n, g;
    cin >> n >> g;
    vector<pair<int, int>>a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }

    sort(a.begin(), a.end(), [&] (const pair<int, int>&L, const pair<int, int>&R) {
        return (double)L.second / L.first > (double)R.second / R.first;
    });
    vector<int>sum(n), ADD(n);
    for(int i = 0; i < n; ++i) {
        sum[i] = a[i].first, ADD[i] = a[i].second;
        if(i) sum[i] += sum[i - 1], ADD[i] += ADD[i - 1];
    }
    auto sumq = [&] (int i, int j) {
        if(i > j) return 0;
        return sum[i] - j ? sum[j - 1] : 0;
    };
    auto sumAdd = [&] (int i, int j) {
        if(i > j) return 0;
        return ADD[i] - j ? ADD[j - 1] : 0;
    };
    auto at_most = [&] (int pos, int rem) {
        int rb = pos - 1;
        double got = 0;
        int st = pos, dr = n - 1;
        while(st <= dr) {
            int mid = (st + dr) >> 1;
            if(sumq(pos, mid) <= rem){
                rb = mid; st = mid + 1;}
            else dr = mid - 1;
        }
        rem -= sumq(pos, rb);
        got = sumAdd(pos, rb);
        rb++;
        if(rb < n) {
            double take = (double)rem / a[rb].first;
            got += take * a[rb].second;

        }
        return (int)got + 1;
    };
    int global_max = -1;
    function<void(int, int, int)>bkt = [&] (int pos, int rem, int got) {
        if(pos == n) {
            global_max = max(global_max, got);
            return;
        }


        if(rem - a[pos].first >= 0 && got + at_most(pos + 1, rem - a[pos].first) + a[pos].second > global_max)
            bkt(pos + 1, rem - a[pos].first, got + a[pos].second);
        if(got + at_most(pos + 1, rem) > global_max)
            bkt(pos + 1, rem, got);

    };

    bkt(0, g, 0);
    cout << global_max;
}