Falling Apart

#include <bits/stdc++.h>
using namespace std;
int t[1000];
int dp[1<<15];
int n;
int f(int x) {
	if(dp[x] != -1) return dp[x];
	int q = __builtin_popcount(x);
	if(q == n) return 0;
	int mi = 1e9;
	int ma = 0;
	for(int i = 0; i < n; ++i) {
		int z = 1<<i;
		if(x&z) continue;
		int w = f(x|z);
		mi = min(w, mi);
		ma = max(w+t[i], ma);
	}
	if(q % 2 == 0) { //alice
		dp[x] = ma;
	}
	else {
		dp[x] = mi;
	}
	return dp[x];
}
int main() {
	cin>>n;
	memset(dp, -1, sizeof dp);
	int sum = 0;
	for(int i = 0; i < n; ++i) {
		cin>>t[i];
		sum += t[i];
	}
	f(0);
	cout<<dp[0]<<' '<<sum-dp[0]<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED