SPOJ BOBERT - Stick values

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long int int64;

typedef vector<int> VI;
typedef vector<VI> VVI;

const int64 INF = 1000000001;

struct maxspt{
    VVI maxarr;
    maxspt(int n, int64* arr){
        int k = (int)log2((double)n+0.2);
        maxarr = VVI(n, VI(k+1));
        for(int lx = 0;lx < n;lx++) maxarr[lx][0] = arr[lx];
        for(int lx = 1;lx <= k;lx++)
            for(int ly = 0;ly+(1<<(lx-1)) < n;ly++)
                maxarr[ly][lx] = max(maxarr[ly][lx-1], maxarr[ly+(1<<(lx-1))][lx-1]);
        return;
    }
    int query(int a, int b){
        int k = (int)(log2(b-a+1.2));
        return max(maxarr[a][k], maxarr[b-(1<<k)+1][k]);
    }
};

struct minspt{
    VVI minarr;
    minspt(int n, int64* arr){
        int k = (int)log2((double)n+0.2);
        minarr = VVI(n, VI(k+1));
        for(int lx = 0;lx < n;lx++) minarr[lx][0] = arr[lx];
        for(int lx = 1;lx <= k;lx++)
            for(int ly = 0;ly+(1<<(lx-1)) < n;ly++)
                minarr[ly][lx] = min(minarr[ly][lx-1], minarr[ly+(1<<(lx-1))][lx-1]);
        return;
    }
    int query(int a, int b){
        int k = (int)(log2(b-a+1.2));
        return min(minarr[a][k], minarr[b-(1<<k)+1][k]);
    }
};

int64 dp[1<<20] = {0};
bool vis[1<<20] = {0};
int64 stl[30];
int64 arr[100000];


int main(){
    int n, s;
    scanf("%d", &n);
    for(int lx = 0;lx < n;lx++) scanf("%lld", arr+lx);

    maxspt maxtb(n, arr);
    minspt mintb(n, arr);

    scanf("%d", &s);
    for(int lx = 0;lx < s;lx++) scanf("%lld", stl+lx);

    queue<int> que;
    que.push(0);
    while(que.size()){
        int sts = que.front(); que.pop();
        int64 len = 0; for(int lx = 0;lx < s;lx++) if(sts&(1<<lx)) len += stl[lx];
        for(int lx = 0;lx < s;lx++){
            if(sts&(1<<lx)) continue;
            int nsts = sts|(1<<lx);
            if(stl[lx]) dp[nsts] = max(dp[nsts], dp[sts] + ((int64)(maxtb.query(len, len+stl[lx]-1) - mintb.query(len, len+stl[lx]-1)))*stl[lx]);
            else dp[nsts] = max(dp[nsts], dp[sts]);
            if(!vis[nsts]){
                que.push(nsts);
                vis[nsts] = 1;
            }
        }
    }
    printf("%lld\n", dp[(1<<s)-1]);
    return 0;
}