JOI 14 予選 Treasures ( MLE Discretized Segment Tree )

Treasures | Aizu Online Judge
It's easy to see that we will have to split them into two equal size sets and update the answer for each set to set. Since there are three options for each item, we will have to enumerate all 3 ^ |s| possible permutations of whether the item is taken, and who had taken it. The range can go up to [ -1e16, 1e16 ] so we have to discretize the range before maintaining on segment tree. Here's what I tried with my usual discretized segment tree which only consume memory when new nodes will be used. However, it will get TLE and MLE in this problem because still to many unused nodes there are. Discretizing indexes beforehand which will ensure that all nodes in the segment tree is used will be more suitable.

// MLE + TLE
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30 + 2;
typedef long long ll;
const ll MAXD = 1e15 + 5;
const ll INF = 1e16;

void upmax(ll &x, ll v){ if( x < v ) x = v; }

int n;
ll d;
ll x[ MAXN ], y[ MAXN ];

struct itvt{
    ll maxv;
    ll lb, rb;
    itvt *lc, *rc;
    itvt(ll _l = -1, ll _r = -1): maxv( -INF ), lb(_l), rb(_r), lc(NULL), rc(NULL){}
    void pull(){
        maxv = -INF;
        if( lc ) upmax( maxv, lc->maxv );
        if( rc ) upmax( maxv, rc->maxv );
    }
    void update(ll k, ll v){
        if( lb == rb ){
            upmax( maxv, v );
            return;
        }
        ll mid;
        if( lb + rb >= 0 ) mid = ( lb + rb ) / 2;
        else mid = ( lb + rb - 1 ) / 2;
        if( k <= mid ){
            if( !lc ) lc = new itvt( lb, mid );
            lc->update( k, v );
        } else{
            if( !rc ) rc = new itvt( mid + 1, rb );
            rc->update( k, v );
        }
        pull();
    }
    ll qmax(ll ql, ll qr){
        if( qr < lb || rb < ql ) return -INF;
        if( ql <= lb && rb <= qr ) return maxv;
        ll res = -INF;
        if( lc ) upmax( res, lc->qmax( ql, qr ) );
        if( rc ) upmax( res, rc->qmax( ql, qr ) );
        return res;
    }
};

void solve(){
    itvt *root = new itvt( (ll)( -INF ), (ll)( INF ) );
    ll ans = 0LL;
    int s0 = n / 2;
    int seq = 1; for(int i = 0; i < s0; ++i) seq *= 3;
    for(int i = 0; i < seq; ++i){
        ll da = 0LL, db = 0LL; // difference in 2 people
        int s = i;
        for(int j = 0; j < s0; ++j){
            if( s % 3 == 1 ) // bruno takes, bruno wants max{ b2 - b1 } under an's condition
                da += x[ j ], db += y[ j ];
            if( s % 3 == 2 ) // anna takes, note anna wants abs( a1 - a2 ) ≤ d
                da -= x[ j ], db -= y[ j ];
            s /= 3; // if s % 3 == 0 not gonna take
        }
        root->update( da, db );
    }
    int s1 = n - s0;
    seq = 1; for(int i = 0; i < s1; ++i) seq *= 3;
    for(int i = 0; i < seq; ++i){
        ll da = 0LL, db = 0LL;
        int s = i;
        for(int j = 0; j < s1; ++j){
            if( s % 3 == 1 ){
                da += x[ s0 + j ], db += y[ s0 + j ];
            }
            if( s % 3 == 2 )
                da -= x[ s0 + j ], db -= y[ s0 + j ];
            s /= 3;
        }
        ll maxs0db = root->qmax( -( da + d ), -( da - d ) );
        ans = max<ll>( ans, db + maxs0db );
    }
    printf("%lld\n", ans);
}

int main(){
    scanf("%d", &n);
    scanf("%lld", &d);
    for(int i = 0; i < n; ++i)
        scanf("%lld%lld", &x[ i ], &y[ i ]);
    solve();
    return 0;
}