No.1882 Areas of Triangle
タグ : / 解いたユーザー数 78
作問者 :
matcharate12
/ テスター :
ripity
Problem Statement
You are given a sequence $A=(A_1,A_2,...A_N)$ of length $N$.
You now choose $2$ integers $i,j$ between $1$ and $N$, inclusive ($i=j$ is allowed), make a right triangle with height $A_i$ and width $A_j$, and measure its area.
How many ways are there to choose $(i,j)$ such that this area is at least $K$? Here, when $i≠j$, $(i,j)$ and $(j,i)$ are considered different.
The area of a right triangle is calculated by the following formula (area $S$ for height $a$ and width $b$): $S=\frac{1}{2}ab$
Input
$N\ K$ $A_1\ A_2\ \dots\ A_N$
Constraints
- $2\le N\le 10^5$
- $1\le K\le 5\times 10^{17}$
- $1\le A_i\le 10^9$
Output
Output the answer.
Sample
Sample 1
Input
3 4 2 5 1
Output
3
The $3$ pairs $(i,j)=(1,2),(2,1),(2,2)$ satisfy the condition, and the areas for these pairs are $5,5,12.5$, respectively. Even if the area is not an integer, the pair counts as long as the area is at least $K(=4)$.
Sample 2
Input
3 5 1 1 2
Output
0
No pair satisfies the condition.
Sample 3
Input
10 95 72 16 43 90 11 7 8 1 9 16
Output
49
Sample 4
Input
3 99999999 10000000 100000000 10000
Output
8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。