NTHUGE - Cái túi 3

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define long long long
#define ii pair<long, long>
#define X first
#define Y second
const int N = 32;
const int NN = (1 << (N / 2)) + 2;

using namespace std;
long res, L, R;
int n, lim, m;
ii a[N], s[NN];
long M[NN][20];

void Gen(int i, long w, long v) {
    if (i > lim) {
        s[++m] = ii(w, v);
        return;
    }
    Gen(i + 1, w, v);
    Gen(i + 1, w + a[i].X, v + a[i].Y);
}

void InitRMQ() {
    int i, j;
    for(i = 1; i <= m; i++) M[i][0] = s[i].Y;
    for(j = 1; (1 << j) <= m; j++)
    for(i = 1; i + (1 << (j - 1)) <= m; i++)
        M[i][j] = max(M[i][j - 1], M[i + (1 << (j - 1))][j - 1]);
}

long get_max(int i, int j) {
    int k = log2(j - i + 1);
    return max(M[i][k], M[j - (1 << k) + 1][k]);
}

int BSL(long w) {
    int l = 1, r = m, mid, k = 0;
    while (l <= r) {
        mid =  l + r >> 1;
        if (s[mid].X >= w) {
            k = mid; r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return k;
}

int BSR(long w) {
    int l = 1, r = m, mid, k = 0;
    while (l <= r) {
        mid = l + r >> 1;
        if (s[mid].X <= w) {
            k = mid; l = mid + 1;
        }
        else
            r = mid - 1;
    }
    return k;
}

void Upd(long w, long v) {
    int head = BSL(L - w), tail = BSR(R - w);
    if (head == 0 || tail == 0) return;
    res = max(res, v + get_max(head, tail));
}

void Back(int i, long w, long v) {
    if (i > n) Upd(w, v);
    else {
        Back(i + 1, w, v);
        Back(i + 1, w + a[i].X, v + a[i].Y);
    }
}

int main()
{
    cin >> n >> L >> R;
    for(int i = 1; i <= n; i++) //scanf("%lld %lld", &a[i].X, &a[i].Y);
        cin >> a[i].X >> a[i].Y;
    lim = n / 2 - 1;
    Gen(1, 0, 0);
    sort(s + 1, s + 1 + m);
    InitRMQ();
    Back(lim + 1, 0, 0);
    cout << res << endl;
    return 0;
}

Download