Model Solution of GEEK04

geek04.cpp

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> a;
int dp[1<<20][2];

int rec(int lft_mask, int turn) {
	if (lft_mask == 0) {
		return 0;
	}
	// cerr << lft_mask << " " << turn << "\n";
	int &res = dp[lft_mask][turn];
	if (res != -1) {
		return res;
	}
	if (turn) {
		int pos = -1;
		res = INT_MAX;
		int rgt_mask = ((1<<n) - 1) ^ lft_mask;
		for(int i = 0; i < n; ++i) {
			if (rgt_mask & (1<<i)) {
				if (res > a[i]) {
					pos = i;
					res = a[i];
				}
			}
		}
		res += rec(lft_mask ^ (1<<pos), turn ^ 1);
	}
	else {
		if (__builtin_popcount(lft_mask) == 1) {
			res = INT_MAX;
			for(int i = 0; i < n; ++i) {
				if (lft_mask & (1<<i)) {
					res = min(res, a[i]);
					res += rec(lft_mask ^ (1<<i), turn ^ 1);
				}
			}
		}
		else {
			res = INT_MAX;
			for(int i = 0; i < n; ++i) {
				if (lft_mask & (1<<i)) {
					for(int j = i+1; j < n; ++j) {
						if (lft_mask & (1<<j)) {
							int lft = lft_mask ^ (1<<i) ^ (1<<j);
							int val = max(a[i], a[j]) + rec(lft, turn ^ 1);
							res = min(res, val);
						}
					}
				}
			}
		}
	}
	assert(res >= 0);
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	assert(1 <= t && t <= 10);
	while(t--) {
		cin >> n;
		assert(1 <= n && n <= 20);
		a.resize(n);
		for(int i = 0; i < n; ++i) {
			cin >> a[i];
		}
		memset(dp, -1, sizeof(dp));
		cout << rec((1<<n)-1, 0) << "\n";
	}
	return 0;
}

@likecs Can you please tell me why I am getting TLE in last two cases even I have not used recursion
https://www.codechef.com/viewsolution/16377126