| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 14 | 8 | 8 | 61.538% |
The Great Kagura loves the number $S$. In front of her, she has a sequence of integers $a_1, \dots , a_n$. She wants to select a collection of these integers such that the sum of the absolute values of the differences of all pairs of integers in her collection is at most $S$. For example, if her collection is $x,ドル $y,ドル $z,ドル then $|x − y| + |x − z| + |y − z| ≤ S$. She wants to select the largest collection that she can. Can you help her?
The first line of the input contains the two integers $n$ and $S$. The second line of the input contains $a_1, \dots , a_n$.
Output the size of the largest collection of integers from among $a_1, \dots , a_n$ that satisfy the required condition.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $a_i = 1$ |
| 2 | 7 | $a_i ∈ \{1, 2\}$ |
| 3 | 8 | $a_i = i$ |
| 4 | 9 | $n ≤ 20,ドル $a_i ≤ 1,000円,ドル $S ≤ 1,000円,000円,000円$ |
| 5 | 21 | $n ≤ 100,ドル $S ≤ 1,000円,000円,000円$ |
| 6 | 18 | $n ≤ 2000,ドル $S ≤ 1,000円,000円,000円$ |
| 7 | 31 | No further restrictions. |
5 3 1 2 3 4 5
2
One possible collection is 1ドル,ドル 2ドル$. All collections with 3ドル$ elements have the sum of absolute differences at least 4ドル$.
5 4 1 2 3 4 5
3
One possible collection is 1ドル,ドル 2ドル,ドル 3ドル$.
5 1 1 1 1 1 1
5
The entire sequence is a valid collection.
10 7 1 5 3 2 4 3 1 3 2 100
5
One possible collection is 2ドル,ドル 2ドル,ドル 3ドル,ドル 3ドル,ドル 3ドル$.
Contest > infO(1) Cup > infO(1) Cup 2022 C번