問題概要

URL: https://atcoder.jp/contests/ahc043/tasks/ahc043_a

50x50のグリッド上にM人(50～1600人)の家と職場が置かれている。

家と職場が駅と線路を経由して移動することが出来れば家と職場のマンハッタン距離分の収入を得ることが出来る。

駅からマンハッタン距離2以内の家と職場に移動可能。

各ターン、下記の3つの内1つの行動が可能。ターン終了後、家と職場が繋がっている人全員からお金を貰う。

1. 5000円払うことで駅が無い座標に駅を作成する
2. 100円払うことで駅と線路が無い座標に線路を作る
3. 何もしない

初期手持ち金額はK円(11000～20000円)で、800ターン終了時点で手持ちの金額を出来る限り大きくしたい。

順位

プレテスト: 31G 211位

システムテスト: 217位

やったこと

貪欲をひたすら頑張りました。

1. 最も稼げる2点間を繋ぐ
   1. もし800ターン経過後初期Kより稼げなかったら全て-1を出力