| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 56 | 15 | 12 | 25.000% |
당신에게 10ドル^6\times 10^6$ 크기의 정사각형 모양의 격자판 세 개가 주어진다. 각 칸은 $x$좌표와 $y$좌표로 번호가 매겨져 있다. $x$좌표는 맨 왼쪽에서부터 맨 오른쪽까지 1ドル$부터 10ドル^6$으로 매겨져 있고, $y$좌표는 맨 아래에서부터 맨 위까지 1ドル$에서 10ドル^6$으로 매겨져 있다. 당신은 각 칸을 검은색 혹은 흰색으로 칠해야 한다.
세 격자의 격자칸을 색칠하는 예시.
첫 번째 격자판은 아래에서부터 올라오는 히스토그램의 형태를 띄어야 한다. 즉, 어떤 격자칸이 검은색으로 칠해져 있다면, 그 아래의 칸도 검은색으로 칠해져 있어야 한다.
두 번째 격자판은 왼쪽에서부터 오른쪽으로 진행하는 히스토그램의 형태를 띄어야 한다. 즉, 어떤 격자칸이 검은색으로 칠해져 있다면, 그 왼쪽 칸도 검은색으로 칠해져 있어야 한다.
세 번째 격자판은 앞의 두 격자판을 이용해 색칠한다. 어떤 칸 $(x,y)$가 첫 두 격자판에서 모두 검은색으로 색칠되어 있다면, 세 번째 격자판의 칸 $(x,y)$ 역시 검은색으로 색칠한다. 그렇지 않다면, 해당 칸을 흰색으로 색칠한다. 이 세 번째 격자판이 최종 그림이 된다.
당신이 그린 그림을 $N$명이 심사위원에게 심사할 예정이다. 각 심사위원은 그림 내의 특정한 $K\times 1$ 직사각형 영역을 심사에 이용한다. $i$번째 심사위원이 이용하는 직사각형 영역은 $[x_i,x_i+K-1]\times[y_i , y_i]$이다. 각 심사위원들이 심사에 이용하는 직사각형 영역은 겹치지 않는다.
$i$번째 심사위원은 칸 $(x_i,y_i)$와 칸 $(x_i+K-1,y_i)$가 같은 색으로 칠해진 경우 불합격으로 판정한다. 두 칸의 색이 다른 경우에는 합격으로 판정하고, 칸 $(x_i,y_i)$가 흰색으로 칠해진 경우에 $a_i$점을, 검은색으로 칠해진 경우에 $b_i$점을 준다.
심사를 통과하기 위해서는 모든 심사위원에게 합격 판정을 받아야 한다. 이때 그림의 점수는 모든 심사위원들에게 받은 점수의 합이 된다. 심사를 통과하는 가능한 모든 그림에 대해서 받을 수 있는 점수의 최댓값을 구해 보자.
첫 번째 줄에는 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다.
다음 $N$개의 줄 중 $i$번째 줄에는 네 정수 $x_i,ドル $y_i,ドル $a_i,ドル $b_i$가 공백으로 구분되어 주어진다.
심사를 통과하는 그림이 없다면, $-1$을 출력한다.
심사를 통과하는 그림이 있다면, 가능한 그림의 최대 점수를 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 30 | $K=2$; $N \leq 5,000円$ |
| 2 | 30 | $K=2$ |
| 3 | 40 | 추가적인 제약 조건이 없다. |
5 2 1 1 1 2 3 1 1 10 5 1 5 6 2 2 3 2 4 2 5 9
26
6 3 1 1 2 4 5 1 4 9 2 3 7 4 5 3 3 1 1 5 5 7 4 5 6 4
36
10 2 7 2 2 4 4 4 6 3 1 5 1 4 3 5 2 8 5 2 4 3 6 4 4 2 1 2 1 4 5 6 9 7 7 1 6 3 4 3 8 7
51
10 3 4 2 5 2 10 2 8 10 1 2 1 4 12 1 8 6 6 3 7 10 8 1 1 9 11 3 5 5 7 2 10 5 3 3 6 4 4 1 9 4
72
$[x_l,x_r]\times[y_l , y_r]$ 직사각형 영역은 $x_l\le x\le x_r$이고 $y_l\le y\le y_r$인 영역을 의미한다.
University > KAIST > KAIST RUN Spring Contest > 2024 KAIST RUN Spring Contest E번