>546

n=500 C++ 実行くんで0.01sec の解答を貼っておきます。
https://ideone.com/AGkj7D

1行分のデータを2つ組み合わせて2行分のデータを作り、
2行分のデータを組み合わせて4行分のデータを作る、としました。
2行分を組み合わせるときは、片方のスコアを決めると、他方のスコアも決まることを使って、試す組み合わせを減らしました。
一行分のデータは8*4=32bitとして、同じ数字が上下に並んでいるかの判定を&演算一回で済ませるようにしました。
8つの状態を表せるようにしたのは、n>500以上でも計算してみたかったからですが、6*4=24bitでも十分でしたね。