問題一覧 > 通常問題

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$ 個は黒く塗られています。
そこで、$a_{i,j}$ という値を以下の様に定義します。

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

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

入力

$N$ $K$ $P$
$x_1$ $y_1$
・・・・
$x_K$ $y_K$

  • $1≦N, K≦4000$
  • $1≦y_i≦x_i≦N$
  • $0≦P≦10^{18}$

出力

「良い選び方」の通り数を 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もしくは右上の雲マークをクリックしてアカウントを作成してください。