Informatica Online Judge

  지하철 3호선 (L) [1140 / 0474]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 15   Total Tried : 20


The Champion of this Problem (C++) : gs16103 - ms / 1306byte
My Best Submission (C++) : N/A

[koistudy.net (32nd 구재현)]

Background

고양시와 도심, 송파구를 잇는 지하철 3호선은, 매일 많은 사람들을 수송해주는 서울시 교통의 중요한 축중 하나이다.

국토교통부 장관인 재현이는 koistudy에 1호선 2호선 문제가 곧 올라올 예정인데 3호선 문제가 없다는 것을 깨닫고, 급하게 지하철 3호선에 급행 열차를 투입해서 문제 낼 거리를 만들려고 한다.

서울시의 지도가 N*N 격자라고 할때, 지하철 3호선은 N (2 <= N <= 3000) 개의 역으로 구성되어 있으며, i (1 <= i <= N) 번째 역의 위치는 (i,i) 지점이다.

즉, 서울시를 동남방향 사선으로 가로지르는 전철인 것이다. 재현이는 이러한 3호선의 역들 중 K(K <= N, 2 <= K <= 500)개의 역에 급행을 정차시키려고 한다.

하지만, 급행을 정차시키려면 지하철 노선을 변경해야 하기 때문에, 공사 위치에 토지보상금을 지급해야 한다.

i번째 역과 j번째 역(i < j)간에 급행 전철을 건설할 때, (i,i) - (i,j) - (j,i) - (j,j) 를 꼭지점으로 하는 변의 길이가 (j-i+1) 길이인 정사각형만큼의 토지에 공사를 하고, 보상금을 지급해야 한다.



(단, 두번 겹치는 부분은 보상금을 두번 지급한다.)

재현이는 무조건 1번 역과 N번 역에 급행을 정차 시키고, 나머지 역 중 건설비용을 최소화하도록 (K-2)개의 역을 선택해서 이 역에 급행을 정차시키려 한다. 재현이를 도와주자.

Input

첫번째 줄에 N,K가 주어지며, 이후 N개에 줄에 띄어쓰기 없이 N개의 한자리 정수가 주어진다, i번째 줄의 j번째 정수는 (i,j) 격자의 토지보상금이다.

[입력값의 정의역]
2 <= N <= 3,000
2 <= K <= N
0 <= 각 격자의 토지보상금 <= 9

Output

정차시킬 수 있는 최소비용을 출력한다.

IO Example

입력
5 3
31415
92653
58979
32384
62643

출력
95

설명 : 사진과 같은 입력이며, 사진과 같이 선택해서 1,4,5 역에 전철을 건설하면 95의 비용으로 정차시킬 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]