PUCMM333  Dividing Xorland
Xorland is a beautiful Kingdom located in the northern part of the Hispaniola Island. You can picture it as a perfect n x n square. Incredibly, n^2 people live there, each in a perfect 1x1 square. They all have an integer spirit in the range [1, 10^6]. The King died recently and, as is custom, Xorland must be divided into three parts.
Xorlandic people love to apply the Xor operation on their spirits, so it is normal to expect them to use it also to divide the land. Xorland must be divided by two parallel lines. These parallel lines must also be parallel to one side of the square. Each part will be nonempty. To divide the land, this is what they do:
(1) Place two parallel lines inside the square.
(2) Construct a nonempty subset of the spirits of the first part and call it A.
(3) Construct a nonempty subset of the spirits of the second part and call it B.
(4) Construct a nonempty subset of the spirits of the third part and call it C.
(4) Apply the Xor operation on A, on B and on C.
(5) Find the value of Xor(A) + Xor(B) + Xor(C) and call it SUM.
(6) Eat and Drink joyfully for SUM days straight.
Between us, Xorlandic people LOVE eating and drinking! That is why they want to find the partition that yields the greatest sum. Help them! Write a program that finds this number.
Input
The first line of input contains N (3 <= N <= 5), the length of the sides of the squared area. Then follow N lines, each bearing a spirit. Each spirit will be a positive integer in the range [1, 10^6].
Output
Output the greatest sum possible.
Sample Cases
Input 3 1 1 1 2 2 2 3 3 3 Output 9
In this case, the optimal choice is to divide vertically. Column 1 is {1, 2, 3}; Column 2 is {1, 2, 3} and Column 3 is {1, 2, 3}. Taking A = {3}, B = {3} and C{3} we get 3 * Xor{3} = 9, the optimal answer. Note that other subsets may yield 9 as well.
hide comments
miodziu:
20140205 05:51:56
Now I got AC :) Thanks for explanation Mitch. 

Mitch Schwartz:
20140205 05:51:56
Letting A={1,2,3} would result in Xor(A)=0 as you wrote; to get the maximal value of 3, we choose either A={3} or A={1,2}. Same with B and C. Xor is defined in the usual way (extended from binary to nary unambiguously because Xor is commutative). Last edit: 20140205 05:50:32 

miodziu:
20140205 05:51:56
I still can't understand, what is Xor(A)? 

Luis Miguel Ruiz:
20140205 05:51:56
3+3+3. XOR(x) could be only one number of the subset x. You want the maximum value possible Last edit: 20140121 13:10:52 

miodziu:
20140205 05:51:56
When we divide vertically, A=B=C={1,2,3}, but 1 XOR 2 XOR 3 = 0, so the sum=0.

Added by:  Olson Ortiz 
Date:  20130101 
Time limit:  0.411s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC MAWK BC CCLANG CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JSMONKEY KTLN NIM OBJC OBJCCLANG OCT PICO PROLOG PYPY R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Olimpiada de ProgramaciĆ³n PUCMM ACMISC 2013 