USACO 2013 November Contest, Gold Problem 3. No Change

http://usaco.org/index.php?page=viewproblem2&cpid=348

Tips : 位元dp + binary search

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

const int MAX_N = 1e5 + 6;
const int MAX_K = 21;

int a[MAX_N];
int p[MAX_K];
int pre[MAX_N];
int dp[(1<<MAX_K)];
int n,k;

int f(int s,int p) {
    if (s>n) return n;
//    cout<<"s = "<<s<<" , p = "<<p;
    int L=s-1,R=n+1;
    while (R-L!=1) {
        int mid=(L+R)>>1;
        if (pre[mid] - pre[s-1] <= p) L=mid;
        else R=mid;
    }
//    cout<<" ret = "<<L<<endl;
    //L is the answer
    return L;
}

int main () {
    if (fopen("nochange.in","r")) {
        freopen("nochange.in","r",stdin);
        freopen("nochange.out","w",stdout);
    }
    while (scanf("%d %d",&k,&n) != EOF) {
        memset(dp,0,sizeof(dp));
        for (int x=0;k>x;x++) {
            scanf("%d",&p[x]);
        }
        for (int x=1;n>=x;x++) {
            scanf("%d",&a[x]);
            pre[x] = pre[x-1] + a[x];
        }
        for (int x=1;(1<<k)>x;x++) {
            for (int y=0;k>y;y++) {
                if ((x&(1<<y))!=0) {
                    dp[x] = max(f(dp[x^(1<<y)]+1,p[y]),dp[x]);
                }
            }
//            cout<<"dp[" << x<<"] = " <<dp[x]<<endl;
        }
        int ans=-1;
        for (int x=0;(1<<k)>x;x++) {
            if (dp[x] >= n) {
                int tmp=0;
                for (int y=0;k>y;y++) {
                    if ((x&(1<<y)) == 0) {
                        tmp+=p[y];
                    }
                }
                ans = max(ans,tmp);
            }
        }
        printf("%d\n",ans);
    }
}