## problem

つまり$\mathrm{ans} = \max_{f : N \to 3, f^{-1}(x) \ne \emptyset} \Sigma_{i \lt 3}^{\text{plus}} \Sigma_{j \lt f^{-1}(i)}^{\text{xor}} a_j$ for given $a_i$。

## solution

DP. $O(A^2)$, $A = 256$ is the maximum of elements.

At first, think the simple DP. The function is $\mathrm{dp} : 256 \times 256 \times 256 \times \mathcal{P}(3) \to 2$, the arguments are xor-sum of each group and empty-flags of groups, and the value is whether such a state exists or not. This is updated for each $a_i$, $N$ times.

Let’s reduce the complexity.

• To make empty group is obviously wrong choice to maximize the sum, so we can ignore the restriction.
• When the xor-sums of two groups are known, the xor-sum of the rest group is easily computable. Let $s_0, s_1$ be the known xor-sums, then the unknown xor-sum $s_2 = \Sigma_i^{\text{xor}} a_i \oplus s_0 \oplus s_1$.

So we can do the DP on the function $\mathrm{dp} : 256 \times 256 \to 2$. And the $\mathrm{ans} = \max \{ s_0 + s_1 + (\Sigma_i^{\text{xor}} a_i \oplus s_0 \oplus s_1) \mid \mathrm{dp}(s_0, s_1) = 1 \}$.

## implementation

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
class TrySail { public: int get(vector<int> strength); };

int TrySail::get(vector<int> strength) {
array<array<array<bool,256>,256>,2> dp = {};
array<array<bool,256>,256> & cur = dp[0];
array<array<bool,256>,256> & prv = dp[1];
int acc = 0; for (int x : strength) acc ^= x;
cur[0][0] = true;
for (int x : strength) {
cur.swap(prv);
repeat (i,256) {
repeat (j,256) {
cur[i][j] = false;
}
}
repeat (i,256) {
repeat (j,256) {
if (prv[i][j]) {
cur[i^x][j] = true;
cur[i][j^x] = true;
cur[i][j] = true;
}
}
}
}
int ans = -1;
repeat (i,256) {
repeat (j,256) {
if (cur[i][j]) {
setmax(ans, i+j+(acc^i^j));
}
}
}
return ans;
}