NTHUGE - Cái túi 3

Tác giả: RR

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(long i=a; i<=b; i++)
#define DOWN(i,a,b) for(long i=a; i>=b; i--)
#define CT(x) (x<<1)
#define CP(x) ((x<<1)+1)
#define ll long long
#define F first
#define S second
#define P pair<ll,ll>
using namespace std;

long n,now;
ll l,r,w[40],v[40];
P a[70111];
ll ln[262144],noww,nowv,res;

void inp() {
    cin >>n >>l >>r;
    FOR(i,1,n) cin >>w[i] >>v[i];
}

inline void init(long i,long l,long r) {
    if (l==r) {
        ln[i]=a[l].S;
        return ;
    }
    long mid=(l+r)>>1;
    init(CT(i),l,mid);
    init(CP(i),mid+1,r);
    ln[i]=max(ln[CT(i)],ln[CP(i)]);
}

inline ll get(long i,long l,long r,ll u,ll v) {
    if (v<a[l].F || u>a[r].F) return 0;
    if (u<=a[l].F && a[r].F<=v) return ln[i];
    long mid=(l+r)>>1;
    return max(get(CT(i),l,mid,u,v),get(CP(i),mid+1,r,u,v));
}

inline void dequy(long i,long ct,long rec) {
    if (i==ct+1) {
        if (!rec) {
            now++;
            a[now].F=noww;
            a[now].S=nowv;
        } else {
            res=max(res,nowv+get(1,1,now,l-noww,r-noww));
        }
        
        return ;
    }
    FOR(j,0,1) {
        if (j) { noww+=w[i]; nowv+=v[i]; }
        if (noww<=r) dequy(i+1,ct,rec);
        if (j) { noww-=w[i]; nowv-=v[i]; }
    }
}

void solve() {
    long nn=n/2+n%2;
    noww=0; nowv=0; dequy(1,nn,0);
    sort(a+1,a+now+1);
    init(1,1,now);
    
    noww=0; nowv=0; dequy(nn+1,n,1);
    cout<<res;
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    inp();
    solve();
    return 0;
}

Download