문제
예술 전시회에서는 아이들이 모래를 사용하여 예술품을 창작할 수 있는 부스를 자주 마련한다. 이 예술은 항아리나 병에 다른 색깔의 모래를 쌓아 층을 만드는 방식으로 만들어진다. 항아리나 병 대신에, 올해에는 새로운 용기가 장식용으로 사용되고 있고, 그 용기는 유리 상자이다.
이 상자는 2D 직사각형 면과 정확히 1단위의 너비를 가지고 있다. 유리 상자 내부에는 n-1개의 수직 칸막이를 배치하여 n개의 구역으로 분리한다. 아래의 예에서, 박스는 3개의 칸막이를 사용하여 4개의 구역으로 나누어진다.
때때로 아이들은 각각의 색이 예술 작품의 각 부분에 적당히 있었으면 한다. 아이들은 각 구역 및 모래 색상의 조합에 대해 최소 및 최대값을 정했다. 당신의 임무는 그들이 작품을 얼마나 균형 있게 만들 수 있는지 알려주는 것이다. 이는 모래가 가장 높은 구간과 모래가 가장 낮은 구간 간의 높이 차이를 최소화시키는 것과 같다.
입력
각 입력은 단일 시험 케이스로 구성된다. 프로그램은 다른 입력으로 여러 번 실행될 수 있다는 점에 유의하자. 각 입력의 첫 번째 줄에는 4개의 공백으로 구분된 정수 n, m, w, h이 주어진다. 이 때, n(2 ≤ n ≤ 200)은 구역 수를, m(1 ≤ m ≤ 200)은 모래의 색상 수를, w와 h (1 ≤ w, h ≤ 5 000)는 상자의 폭과 높이를 의미한다. 깊이는 항상 1이다.
다음 줄에는 각 모래 색깔에 대해, 사용할 수 있는 모래의 양이 공백으로 구분된 m개의 실수 v(0 < v ≤ w·h)가 (소숫점 아래 최대 3자리까지) 주어진다. 모래를 모두 사용할 필요는 없지만 각 구간에 대한 최소값을 만족시켜야 함에 유의하자.
다음 줄에는 구역을 나누는 칸막이의 위치 정보가 n-1의 공백으로 구분된 실수 x가(소수점 이하 3자리까지)주어지며, 정확히는 왼쪽 벽으로부터 칸막이까지의 거리를 의미한다. x는 증가하는 순서대로 주어짐이 보장된다.
다음 n개의 줄에는 각 구역에 사용해야 하는 모래의 최소량에 대한 정보가 n행 m열의 배열로 주어진다. 정확히는, i번째 행 j번째 열에 주어지는 (소수점 이하 3자리까지의)실수 minij는 i번째 구역에 넣을 모래 색 j의 최소량이다.
다음 n개의 줄에는 각 구역에 사용해야 하는 모래의 최대량에 대한 정보가 n행 m열의 배열로 주어진다. 정확히는, i번째 행 j번째 열에 주어지는 (소수점 이하 3자리까지의)실수 maxij는 i번째 구역에 넣을 모래 색 j의 최대량이다. minij ≤ maxij임이 보장된다.
출력
구역 내 모래의 최대 높이와 최소 높이의 차이 최솟값을 소수점 4자리에서 반올림한 실제 숫자를 출력한다. 모래의 분포는 항상 입력의 제약조건을 만족시킬 수 있음이 보장된다.
예제 #1
2 2 5 5
2.0 2.0
4.0
1.0 0.0
0.0 1.0
1.0 0.0
0.0 2.0
0.750
예제 #2
2 2 5 5
2.0 2.0
4.0
1.0 0.0
0.0 1.0
1.5 0.0
0.0 2.0
0.625
예제 #3
2 5 11 10
3.0 4.0 4.0 9.0 2.0
4.0
2.0 2.0 1.0 0.5 0.25
0.0 2.0 0.0 4.0 1.0
2.0 2.0 3.0 4.0 0.75
0.0 2.1 0.0 5.1 1.1
0.266
로그인해야 코드를 작성할 수 있어요.