問題一覧 > 通常問題

No.655 E869120 and Good Triangles

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 17
作問者 : e869120 / テスター : WA_TLE
お気に入りにしたユーザー ProblemId : 1922 / 自分の提出
問題文最終更新日: 2026-06-26 06:07:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 184 (順位表) の他の問題:

Problem Statement

E869120 saw a triangular figure like the one below.

yukicoder_1922_1
In this case, the size of the triangular figure is 4.

Now, there is a triangular figure of size $N$. It has $N*(N+1)/2$ vertices in total, and $K$ of them are painted black.
Define the value $a_{i,j}$ as follows.

  • $a_{i,j}$ = the length of the shortest path from cell $(i, j)$ to the nearest black vertex (every edge has length 1)

E869120 is going to take a "partial equilateral triangle" out of the triangular figure. A "partial equilateral triangle" is something like the first and second figures from the left in the image below. An inverted triangle like the third figure from the left is not counted.
yukicoder_1922_2
A choice is called a "good choice" if the sum of $a_{i,j}$ over the vertices contained in the "partial equilateral triangle" is at least $P$. How many good choices are there?

Input

$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}$

Output

Output the number of "good choices" on one line. Do not forget the trailing newline.

Sample

Sample 1
Input
3 1 6
2 1
Output
1
Sample 2
Input
4 1 4
2 2
Output
8
Sample 3
Input
5 2 8
3 2
4 4
Output
5

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