SUBSUMS - Subset Sums

Given a sequence of N (1 ≤ N ≤ 34) numbers S1, ..., SN (-20,000,000 ≤ Si ≤ 20,000,000), determine how many subsets of S (including the empty one) have a sum between A and B (-500,000,000 ≤ A ≤ B ≤ 500,000,000), inclusive.

Input

The first line of standard input contains the three integers N, A, and B. The following N lines contain S1 through SN, in order.

Output

Print a single integer to standard output representing the number of subsets satisfying the above property. Note that the answer may overflow a 32-bit integer.

Example

Input:

3 -1 2

1

-2

3

Output:

5

The following 5 subsets have a sum between -1 and 2:

0 = 0 (the empty subset)

1 = 1

1 + (-2) = -1

-2 + 3 = 1

1 + (-2) + 3 = 2

Submit solution!

思路：折半枚举+二分；

复杂度O（\(2^ \frac{n}{2}*log(2^ \frac{n}{2})\)）

#include<stdio.h>

#include<algorithm>

#include<iostream>

#include<queue>

#include<string.h>

#include<map>

typedef long long LL;

using namespace std;

int ans[50];

int aa[20],bb[20];

int a1[200000],a2[200000];

int low(int l,int r,int ask);

int high(int l,int r,int ask);

int main(void)

{

    int n,a,b;

    scanf("%d %d %d",&n,&a,&b);

    for(int i = 1; i <= n; i++)

    {

        scanf("%d",&ans[i]);

    }

    int cn = 0;

    for(int i = 1; i <= (n/2); i++)

    {

        aa[cn++] = ans[i];

    }

    cn  = 0;

    for(int i = n/2+1; i <= n; i++)

    {

        bb[cn++] = ans[i];

    }

    int x1 = n/2,x2 = n-x1;

    int cx1 = 0;

    for(int i = 0; i < (1<<x1); i++)

    {

        int sum = 0;

        for(int j = 0; j < x1; j++)

        {

            if(i&(1<<j))

                sum+= aa[j];

        }

        a1[cx1++] = sum;

    }

    int cx2 = 0;

    for(int i = 0; i < (1<<x2); i++)

    {

        int sum = 0;

        for(int j = 0; j < x2; j++)

        {

            if(i&(1<<j))

                sum += bb[j];

        }

        a2[cx2++] = sum;

    }

    sort(a1,a1+cx1);

    sort(a2,a2+cx2);

    LL acc = 0;

    for(int i = 0; i < cx1; i++)

    {

        int asl = a-a1[i];

        int asr = b-a1[i];

        int ll = low(0,cx2-1,asl);

        int rr = high(0,cx2-1,asr);

        if(rr >= ll&&ll!=-1&&rr!=-1)

        {

            acc += (LL)(rr-ll+1);

        }

    }

    printf("%lld\n",acc);

    return 0;

}

int low(int l,int r,int ask)

{

    int id = -1;

    while(l <= r)

    {

        int mid = (l+r)/2;

        if(a2[mid] >= ask)

        {

            id = mid;

            r = mid-1;

        }

        else l = mid+1;

    }

    return id;

}

int high(int l,int r,int ask)

{

    int id = -1;

    while(l <= r)

    {

        int mid = (l+r)/2;

        if(a2[mid] <= ask)

        {

            id = mid;

            l = mid+1;

        }

        else r = mid-1;

    }

    return id;

}

巴特西

spoj-SUBSUMS - Subset Sums

SUBSUMS - Subset Sums

最新文章

热门文章