No.655 E869120 and Good Triangles

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.655 E869120 and Good Triangles

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 :

e869120 / テスター :

WA_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

出力

サンプル2

入力

4 1 4
2 2

出力

サンプル3

入力

5 2 8
3 2
4 4

出力

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