[B1208] - 부분집합의 합2

https://www.acmicpc.net/problem/1208

부분집합의 합 1에 이어 2입니다

이번엔 N이 40이 되었습니다.부분집합의 합 1처럼 모든 경우를 만든다면 틀리겠지만

20개씩 나누어서 각각 부분집합으로 만들 수 있는 수를 배열로 만든 후

sorting하여 합이 S가 되는 경우를 찾으면 됩니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int n,s;
    cin >> n >> s;
    int m = n / 2;
    int l = n - m;
    long long ans = 0;
    
    vector<int>a(m);
    vector<int>up(1 << m);
    vector<int>b(l);
    vector<int>down(1 << l);
 
    for (int i = 0; i < m; i++)
    {
        cin >> a[i];
    }
    for (int i = m,j=0; i < n; i++)
    {
        cin >> b[j++];
    }
    
    for (int i = 0; i < (1 << m); i++)
    {
        for (int k = 0; k < m; k++)
        {
            if (i&(1 << k))
            {
                up[i] += a[k];
            }
        }
    }
    for (int i = 0; i < (1 << l); i++)
    {
        for (int k = 0; k < l; k++)
        {
            if (i&(1 << k))
            {
                down[i] += b[k];
            }
        }
    }
    
    sort(up.begin(), up.end());
    sort(down.begin(),down.end());
    int i = 0;
    int j = (1<<l)-1;
    while (i<(1 << m) &&j>=0)
    {
        
        if (up[i] + down[j] == s)
        {
            long long upcnt = 1;
            long long downcnt = 1;
            i++;
            j--;
            while (i<(1<<m)&&up[i] == up[i - 1])
            {
                upcnt++;
                i++;
            }
            while (j>=0&&down[j] == down[j+ 1])
            {
                downcnt++;
                j--;
            }
            ans += upcnt * downcnt;
        }
        else if (up[i] + down[j] < s)
        {
            i++;
        }
        else if (up[i] + down[j] > s)
        {
            j--;
        }
    }
    if (s == 0)
        ans--;
    cout << ans << '\n';
}