| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 99 | 85 | 66 | 84.615% |
ICPC University has $N$ students, numbered from $1$ to $N$, in its Competitive Programming club. Student $i$ has a rating of $R_i$ representing their estimated skill in competitive problem-solving.
Contest season is coming and Morgan, the coach of the Competitive Programming club, would like to send at most one good team to a particular contest due to their limited budget. A team consists of exactly $3$ different students. Suppose that a team consists of student $i$, $j$, and $k$. Their team rating is $A_i + A_j + A_k$, and their rating difference is $\max(A_i , A_j , A_k) - \min(A_i , A_j , A_k)$.
Morgan believes that a team is balanced if their rating difference is no more than a threshold of $M$. Additionally, he also would like the team rating to be as large as possible while being a balanced team as well.
Morgan asks you to compute two values. The first value is the number of different balanced team configurations that can be made. The second value is the largest team rating of a balanced team that can be made.
Two team configurations are different if and only if there is at least one different student between those team configurations.
Input begins with two integers $N$ $M$ ($3 ≤ N ≤ 200$; $0 ≤ M ≤ 4000$) representing the number of students and the threshold for rating difference, respectively. The next line contains $N$ integers $A_i$ ($0 ≤ A_i ≤ 4000$) representing the rating of student $i$.
If there is at least one balanced team configuration, then output two space-separated integers in a single line representing the number of different balanced team configurations and the largest team rating of any balanced team, respectively.
If there is no balanced team configuration, then output -1 in a single line.
5 150 1400 1425 1250 4000 1300
2 4125
An example of a balanced team configuration is the team consisting of student $1$, $3$, and $5$. Their team rating is $1400 + 1250 + 1300 = 3950$. Their rating difference is $1400 - 1250 = 150$, which is no more than $150$.
The other balanced team configuration is the team consisting of students $1$, $2$, and $5$. Their rating difference is $125$ with a team rating of $4125$, which is the highest team rating among all balanced team configurations that can be made.
4 100 2000 1900 1800 2100
-1
Any team configuration has a rating difference of at least $200$, which is more than the given threshold.
8 4000 100 200 300 400 500 600 700 800
56 2100
Any team configuration in this example is a balanced team, while the team consisting of students $6$, $7$, and $8$ has the largest team rating of $600 + 700 + 800 = 2100$.
8 0 10 10 10 20 20 20 30 30
2 60
There are only $2$ possible balanced team configurations: A team with students $1$, $2$, and $3$ with a total team rating of $10 + 10 + 10 = 30$, and a team with students $4$, $5$, and $6$ with a total team rating of $20 + 20 + 20 = 60$. The latter has the largest team rating.
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2022 A번
ICPC > Regionals > Asia Pacific > Indonesia > Indonesia National Contest > INC 2023 연습 세션 PA번