I - その味は甘くて
Editorial
/
突然だが,あなたはとある養蜂家専属のプログラマである.ある日,巣で生成されるハチミツの糖度を管理するために,次のようなプログラムを作成するよう求められた.
下図のような正六角形が敷き詰められた座標系を考える.
指定された座標系の上に,蜂の巣の情報が与えられる.蜂の巣は,巣のタイプと中心部の座標,および大きさから成る.巣のタイプによって,巣に含まれる六角形がどのような糖度を持つかが異なる.
例えば,大きさが 3 である各タイプの巣に含まれる六角形の糖度は,以下の図のように加算される.
また,六角形が複数の巣に含まれる場合は,その部分の糖度は各巣についての糖度の和になる.最大の糖度を持つ部分の糖度を出力せよ.
入力は以下の形式で標準入力から与えられる.
最も糖度の高い六角形の糖度を1 行に出力せよ.
なお、最後には改行を出力せよ.
10 点分については,入力の条件に加え,以下の条件を全て満たす.
50 点分については,入力の条件に加え,以下の条件を全て満たす.
タイプ3,大きさ4の巣の最大糖度は 16 である.
複数の巣が重なる場合,その部分の糖度は各巣についての糖度の合計になる.
巣の様子は以下の図のようになる.
Time Limit: 5 sec / Memory Limit: 512 MB
問題
指定された座標系の上に,蜂の巣の情報が与えられる.蜂の巣は,巣のタイプと中心部の座標,および大きさから成る.巣のタイプによって,巣に含まれる六角形がどのような糖度を持つかが異なる.
- タイプ1 : 巣に含まれる全ての六角形に一様に糖度 1 が加算される.
- タイプ2 : 大きさを n,中心からの距離を d とすると,糖度 n-d が加算される.
- タイプ3 : 大きさを n,中心からの距離を d とすると,糖度 (n-d)^2 が加算される.
例えば,大きさが 3 である各タイプの巣に含まれる六角形の糖度は,以下の図のように加算される.
また,六角形が複数の巣に含まれる場合は,その部分の糖度は各巣についての糖度の和になる.最大の糖度を持つ部分の糖度を出力せよ.
入力
N type_{1} x_{1} y_{1} size_{1} type_{2} x_{2} y_{2} size_{2} ... type_{N} x_{N} y_{N} size_{N}
- 1 行目には蜂の巣の数 N(1 ≦ N ≦ 10,000) が与えられる.
- 2 行目~ N+1 行目には各巣の情報が 1 行ずつ与えられる.
- 各巣の情報はタイプ( type_{i} ),中心座標( x_{i},y_{i} ),および大きさ( size_{i} )から成り,それぞれ半角スペース区切りで与えられる.また,それぞれ以下の条件を満たす.
- 1 ≦ type_{i} ≦ 3
- |x_{i}| ≦ 500
- |y_{i}| ≦ 500
- 1 ≦ size_{i} ≦ 500
出力
なお、最後には改行を出力せよ.
部分点
- 1 ≦ N ≦ 100
- type_{i} = 1
- |x_{i}| ≦ 100
- |y_{i}| ≦ 100
- 1 ≦ size_{i} ≦ 100
50 点分については,入力の条件に加え,以下の条件を全て満たす.
- type_{i} = 1
入力例 1
1 1 0 0 3
出力例 1
1
入力例 2
1 3 -1 -1 4
出力例 2
16
入力例 3
2 1 0 0 3 3 -1 -1 4
出力例 3
17
入力例 4
3 1 0 0 2 1 1 -1 2 1 -1 1 2
出力例 4
3