Intermediate.
Put your skills to the test.

Problem summary

Find the longest run in[k1,k2] not representable by a nonempty subset sum of the signed input values.

Constraints

1<n<500; −30000<k1<k2<30000; −1000≤a[i]≤1000.

Worked example

Input and output for the worked example discussed below.

5 -7 11
4 -2 3 -5 6

1

Solution analysis

1. All subset sums fit within±499000. Use a bitset indexed by sum+500000, initially all clear because only nonempty subsets count.
2. For each x, retain old sums and add their shifted copy by x, then mark singleton x. Positive x shifts left, negative x shifts right. The shifted expression uses the old state, preventing reuse of x.
3. Scan the requested interval for the longest clear-bit run. The sample maximum is1. Zero becomes representable only if a nonempty subset genuinely sums to zero, not through an empty-subset initialization.

Why it works

Every nonempty subset omits the new value, is its singleton, or extends a previous nonempty subset. The update covers exactly these cases, proving the bitset by induction.

Watch out. Do not initialize an empty zero sum. Signed sums need the offset and opposite shift directions.

An independently written complete program with standard headers.

#include<iostream>
#include<set>
#include<bitset>
#include<algorithm>
using namespace std;
// Every nonempty subset omits the new value, is its singleton, or extends a previous nonempty subset.
int main(){
    const int offset=500000;
    int n,left,right;
    cin>>n>>left>>right;
    bitset<1000001>reachable;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(x>=0){
            reachable|=reachable<<x;
        }
        else{
            reachable|=reachable>>(-x);
        }
        reachable.set(offset+x);
    }
    int current=0,answer=0;
    for(int x=left;x<=right;x++){
        if(reachable[offset+x]){
            current=0;
        }
        else{
            current++;
            answer=max(answer,current);
        }
    }
    cout<<answer<<'\n';
}