| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 85 | 73 | 55 | 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번