시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 308 | 193 | 151 | 60.400% |
과거 카자흐스탄에는 "실크로드"라는 교역로가 있었다.
실크로드는 N + 1 개의 도시가 있고, 서쪽부터 도시 0, 도시 1, ..., 도시 N이다. 도시 i - 1과 도시 i (1 ≦ i ≦ N) 사이의 거리는 Di이다.
무역상인 JOI 군은 도시 0에서 출발하여 도시를 차례로 경유하여 도시 N까지 실크로드를 수행하게 되었다. 도시 0에서 도시 N까지 M 이내에 이동해야한다. JOI 군은 각각의 날에 다음 두 가지 중 하나를 선택한다.
그러나, 이동 할 때마다 피로도가 쌓여 간다. 실크로드에서는 매일 날씨변화가 나쁜 정도에 따라 이동에 어려움이 측정된다.
JOI 군은 M 일 중 j 일째 (1 ≦ j ≦ M)의 날씨가 Cj임을 알고있다. 도시 i - 1에서 도시 i (1 ≦ i ≦ N)에 j 일째 (1 ≦ j ≦ M)로 이동하는 경우, 피로도가 Di × Cj 만 쌓여 버린다. 이동하지 않고 기다리는 날은 피로도가 쌓이지 않는다.
JOI 군은 각각의 날에 행동을 잘 선택하여 가능한 피로도를 적게해서 이동하고 싶다. JOI 군이 M 이내에 도시 N으로 이동할 때의 피로도 총합의 최소를 구해라.
입력은 1 + N + M 행으로 구성된다.
첫 번째 줄에는 두 개의 정수 N, M (1 ≦ N ≦ M ≦ 1000)가 공백을 구분으로 쓰여져있다. 이것은 실크로드가 N + 1 개의 도시로 구성되며, JOI 군이 실크를 도시 0에서 도시 N까지 M 이내에 실시해야한다는 것을 나타낸다.
다음 N 라인 중 i 번째 줄 (1 ≦ i ≦ N)에는 정수 Di (1 ≦ Di ≦ 1000)가 적혀있다. 이것은 도시 i - 1과 도시 i 사이의 거리가 Di임을 나타낸다.
다음 M 라인 중 j 번째 줄 (1 ≦ j ≦ M)에는 정수 Cj (1 ≦ Cj ≦ 1000)가 적혀있다. 이것은 j 일째 날씨 나쁨정도가 Cj임을 나타낸다.
JOI 군이 M 이내에 도시 N으로 이동할 때의 피로도 총합의 최소를 한 줄로 출력한다.
3 5 10 25 15 50 30 15 40 30
1125
2 6 99 20 490 612 515 131 931 1000
31589
입출력 예 1에서 쌓이는 피로도의 합계를 최소화하도록 JOI 군이 이동하려면 다음과 같이한다.
JOI 군이 이렇게 이동 한 경우에 쌓이는 피로도의 합계는 300 + 375 + 450 = 1125이다. 이것이 최소이다.