Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Need help with meet in the middle question from Cses : Timeout error

Revision en1, by qwerty29, 2021-05-16 15:47:35

Question: https://cses.fi/problemset/task/1628/

You are given an array of n numbers. In how many ways can you choose a subset of the numbers with sum x?

Solution: Using meet in the middle approach but its timing out for few test cases, could you please help me where I can improve my code.

#include <bits/stdc++.h>
#define all(c) (c).begin(), (c).end()
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c),x) != (c).end())
#define fi first
#define se second
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define parr(arr) for(int num : (arr)) cout << num << ' '; cout << '\n';
using namespace std;


int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
        int n; cin >> n;
        long long int x; cin >> x;
        int mid = n/2;
        vector<int> arr(n);
        for(int i=0;i<n;++i) cin >> arr[i];
        vector<long long int> left, right;
        for(int i=0;i<(1<<mid);++i){
            long long int sum = 0;
            for(int j=0;j<32;++j){
                if(i & (1<<j)){
                    sum += arr[j];
                }
            }
            left.push_back(sum);
        }
        int rem = n-mid;
        for(int i=0;i<(1<<rem);++i){
            long long int sum =0;
            for(int j=0;j<32;++j){
                if(i & (1<< j))
                    sum += arr[mid+j];  
            }
            right.push_back(sum);
        }
        long long int count = 0;
        unordered_map<long long int,int> m;
        for(int num : right) m[num]++;
        for(int i=0;i<left.size();++i){
            if(left[i] <= x){
                long long int other = x - left[i];
                count += m[other];
            }
        }
        cout << count << '\n';
    return 0;
}
Tags meet in the middle

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English qwerty29 2021-05-16 15:47:35 1901 Initial revision (published)