개발자 크루
남양연구소
남양연구소입니다.
Lv. 5
복잡한 조립라인2
- 난이도
- 5 단계
- 참가자
- 0 명
- 제출
- 0 명
- 정답률
- 0.00 %
언어별 시간/메모리
| 언어 | 시간 | 메모리 |
|---|---|---|
| JavaScript | 2초 | 256MB |
| C | 1초 | 256MB |
| C++ | 1초 | 256MB |
| Java | 2초 | 256MB |
| Python | 2초 | 256MB |
동일한 자동차를 생산하는 K개의 조립라인 Li (1 ≤ i ≤ K)가 있다. 한 조립라인에는 각각 N개의 작업장이 있다. 각각의 작업장을 Li,j (1 ≤ i ≤ K, 1 ≤ j ≤ N)로 표시하자.
모든 라인의 j번째 작업장은 동일한 작업을 수행하지만 작업 시간은 다를 수 있다. 모든 조립라인은 1번 작업장에서 최초 조립이 시작되며, j번째 작업장에서 작업이 종료되면 바로 j+1번째 작업장에서 작업을 시작할 수 있다.
Li,j 작업장에서 LK,j+1(i ≠ K) 작업장으로 이동이 가능한데 j값이 같으면 이동 시간은 모두 동일하다. 자동차 1대의 가장 빠른 조립 시간을 구하여라.
제약조건
1 ≤ N ≤ 102 인 정수
1 ≤ K ≤ 104 인 정수
각 작업시간과 이동시간은 105을 넘지 않는 양의 정수
입력형식
첫 번째 줄에 라인의 수 K와 작업장의 수 N이 주어진다.
j+1 (1 ≤ j ≤ N-1) 번째 줄에는 Li,j (1 ≤ i ≤ K) 작업장의 작업시간이 i의 오름차순으로 주어지고, Li,j 작업장에서 LK,j+1 (K ≠ i) 작업장까지 이동시간이 주어진다.
출력형식
첫 번째 줄에 가장 빠른 조립시간을 출력하라.
입력예제1
2 2 1 3 2 10 2
출력예제1
5