ACPC2012Day2OL C.War

問題

ある無限に広い2次元グリッドの、あるマスにいる。兵士をn人つれており、各兵士の体力が与えられる。
各兵士は上下左右の隣接マスに移動できるが体力が1減る。
通ったマスを占領できるとき、最大でいくつのマスを占領できるか。

考え方

最初に降順にソートしておく。
最初の4人は、スタートマスから上下左右にまっすぐ進めばよい。
5人目からは、点対称になるように最初にのばしたマスのすぐ横にのびるようにマスを進める。なので、兵士の体力-1分マスをのばせる。
9人目からは、同様に5〜8人目でのばしたマスのすぐ横をのばすようにマスを進めればよい。なので、兵士の体力-2分マスをのばせる。
これを繰り返し、4人ごとに重複するマスの分を減らしていって、その合計値をもとめればよい。

ただし、体力と人数から64bit整数でないとオーバーフローするので気をつける。