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;
}