CSES Task 1628, Meet in the Middle

Problems and Contests
#1

Here is the problem. Below is my code.

/*
Author: atharvd
Date:
Problem:
*/

#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<functional>
#include<numeric>
#include<cmath>
#include <climits>

using namespace std;

#define ain(a) for(int i=0;i<a.size();i++) cin >> a[i]
#define aout(a) for(int i=0;i<a.size();i++) { if(i > 0) cout << " "; cout << a[i]; }; cout << endl
#define couty cout << "YES\n"
#define coutn cout << "NO\n";

#define endl "\n"

#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()

#define nl cout << endl

#define add(m, e) if(m.find(e) == m.end()) m[e] = 0; m[e]++;
#define precision(x) printf("%.12f\n", x);

#ifdef LOCAL_JUDGE
#include "local.hpp"
#else
template <typename Head, typename... Tail> void dout(Head&& h, Tail&&... t) {}
#endif

typedef long long ll;
#define int ll
typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef tuple<ll,int,int> tllii;
typedef vector<int> vi; typedef vector<bool> vb; typedef vector<ll> vll; typedef vector<vector<int> > vvi;

ll inf = 1e18 + 1;

map<int, int> freq1;
map<int, int> freq2;

void search1(vi arr, int k, int s){
    if(k == arr.size()){
        freq1[s]++;
    }
    else{
        search1(arr, k + 1, s);
        search1(arr, k + 1, s + arr[k]);
    }
}

void search2(vi arr, int k, int s){
    if(k == arr.size()){
        freq2[s]++;
    }
    else{
        search2(arr, k + 1, s);
        search2(arr, k + 1, s + arr[k]);
    }
}

void solve() {
    int n, x;
    cin >> n >> x;
    vll arr1;
    vll arr2;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        if(i % 2 == 0) arr1.pb(a);
        else arr2.pb(a);
    }
    search1(arr1, 0, 0);
    search2(arr2, 0, 0);
    ll ans = 0;
    for(auto [a, b]: freq1){
        if(freq2.find(x - a) != freq2.end()){
            ans +=  b * freq2[x - a];
        }
    }
    cout << ans << endl;
}

signed main(signed argc,char *argv[]){
#ifdef LOCAL_JUDGE
	freopen(argc > 1 ? argv[1] : "in.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
 
	int t = 1;
	//cin >> t;
	for(int i=1;i<=t;i++) {
		dout("***",i);
		solve();
	}
}

I get a timeout despite using the meet in the middle strategy, can anyone tell me how to optimize this? I know the code is not the best.

#2

Use PBDS with custom hash. Besides, a recursive function search slows down your program. Try to use a while loop.

1 Like