問題一覧 > 通常問題

No.655 E869120 and Good Triangles

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : e869120e869120 / テスター : WA_TLEWA_TLE
1 ProblemId : 1922 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-03-09 21:28:32

問題文

E869120 君は、以下のような三角図形を見ました。

yukicoder_1922_1
この場合三角図形の大きさは 4 です。

さて、大きさ N の三角図形がありました。全部で N(N+1)/2 個の頂点がありますが、そのうち K 個は黒く塗られています。
そこで、ai,j という値を以下の様に定義します。

  • ai,j = マス (i,j) から最寄りの黒い頂点までの最短経路の長さ (全ての辺の長さは 1)

E869120 は、その三角図形の中から「部分正三角形」を取り出そうとしています。「部分正三角形」とは下図の左から 1, 2 番目のようなものです。左から 3 番目のような逆三角形は数えられません。
yukicoder_1922_2
「部分正三角形」の中に含まれる頂点に対応する ai,j の和が P 以上の時、「良い選び方」とします。良い選び方は何通りあるのでしょうか。

入力

N K P
x1 y1
・・・・
xK yK

  • 1N,K4000
  • 1yixiN
  • 0P1018

出力

「良い選び方」の通り数を 1 行に出力してください。最後の改行を忘れずに。

サンプル

サンプル1
入力
3 1 6
2 1
出力
1
サンプル2
入力
4 1 4
2 2
出力
8
サンプル3
入力
5 2 8
3 2
4 4
出力
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。