| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 72 | 35 | 31 | 64.583% |
GIST는 리버럴 아츠 칼리지 모델을 차용하여 학부생들에게 수준 높은 인문학/사회학 교양과목을 제공하고 있다.
2024년, GIST는 교양으로 마법학 과목을 신설했다. GIST 부지 내에는 $N$개의 마법원이 있고, 각각의 마법원은 좌표평면 위 하나의 점으로 표현된다. 마법원들은 각각 마나의 세기와 색깔을 가진다. 마나의 세기는 양수이고, 색깔은 1ドル$과 $K$ 사이의 정수로 표현할 수 있다. 기초마법학 수업의 일환으로 마법진 그리기를 배우고 있는 해원이는 다음 조건을 만족시키며 마법진을 그려야 한다.
마법진의 힘은 직사각형의 내부 또는 네 변의 위에 있는 모든 마법원의 마나의 세기의 총합이다. 만약 마법진 내에 하나의 마법원도 포함되어 있지 않다면, 마법진의 힘은 0ドル$이다. 마법진의 힘을 최대화하시오.
첫째 줄에 마법원의 개수 $N$과 마법원 색깔의 종류의 수 $K$가 공백으로 구분되어 주어진다. (2ドル \leq N \leq 150,000円,ドル 2ドル \leq K \leq \min\left\{N,10,000円\right\}$)
둘째 줄부터 $N$개의 줄에 걸쳐 네 정수 $x_i, y_i, p_i, c_i$가 공백으로 구분되어 주어진다. (1ドル \leq x_i, y_i \leq 10^8,ドル 1ドル \leq p_i \leq 1,000円,ドル 1ドル \leq c_i \leq K$) 이는 $i$번째 마법원이 좌표 $(x_i, y_i)$에 위치하고, 마나의 세기 $p_i$를 가지며, $c_i$번째 색깔을 가진다는 뜻이다.
1ドル$ 이상 $K$ 이하의 모든 정수 $j$에 대하여 $j$번째 색깔을 가지는 마법원이 적어도 하나 존재한다.
$x$좌표와 $y$좌표가 모두 같은 마법원이 두 개 이상 존재할 수 있음에 주의하시오.
주어진 조건을 만족시키며 그릴 수 있는 마법진 힘의 최댓값을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 30 | $N \leq 300$ |
| 2 | 15 | 모든 마법원의 $y$좌표가 1ドル$이다. |
| 3 | 55 | 추가 제약 조건이 없다. |
6 3 1 3 2 1 2 2 3 1 3 1 4 1 2 3 2 3 3 2 5 3 3 3 8 2
12
10 4 5 1 5 1 2 5 1 2 2 6 2 4 3 6 9 3 3 5 1 2 5 8 8 4 6 4 10 3 7 6 6 2 4 7 7 2 2 1 6 1
23
2 2 1 1 1 1 1 1 1 2
0
이 예제과 같이 $x$좌표와 $y$좌표가 모두 같은 마법원이 두 개 이상 존재할 수 있음에 주의하시오.
University > 광주과학기술원 > 2024 GIST 알고리즘 마스터즈 H번