시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 269 | 87 | 54 | 27.411% |
양의 정수로 구성된 길이 N인 수열 A와 길이 M인 수열 B가 있다. 두 수열에 대해서 게임을 진행하려 한다.
수열 A의 뒤에서부터 K1(≥ 1)개의 수들의 합을 S1이라 하고, 수열 B의 뒤에서부터 K2(≥ 1)개의 수들의 합을 S2라 하자. 한 개의 수를 선택할 수도 있고, 수열 전체를 선택할 수도 있다. 이 단계에서의 점수는 (S1 - K1) × (S2 - K2)가 된다. 이때 선택한 수들을 원래 수열에서 제거한다. 즉, 수열 A의 뒤에서부터 K1개의 수들을 제거하고, 수열 B의 뒤에서부터 K2개의 수들을 제거한다. 그리고 남아있는 수열에 대해서 같은 방식으로 게임을 진행한다. 게임은 두 수열을 이루는 수들이 모두 제거됐을 때 끝난다. 이와 같이 게임을 진행했을 때의 전체 점수는, 각 단계에서의 점수의 총 합이 된다.
두 수열이 주어졌을 때, 전체 점수의 최소를 구하는 프로그램을 작성하시오.
수열에서 수들을 제거할 때 1개 이상씩 제거를 하게 된다. 또한 게임은 두 수열을 이루는 수들이 모두 제거됐을 때 끝난다. 즉, 하나의 수열은 모두 제거됐는데 다른 하나의 수열은 모두 제거되지 않은 경우는 게임이 끝난 경우가 아니다. 즉, 하나의 수열만 남게 되는 경우가 있어서는 안 된다.
첫째 줄에 두 정수 N, M(1 ≤ N, M ≤ 2,000)이 주어진다. 다음 줄에는 A를 이루는 수들이 앞에서부터 주어진다. 그 다음 줄에는 B를 이루는 수들이 앞에서부터 주어진다. 두 수열을 이루는 수들은 모두 1,000이하이다.
첫째 줄에 전체 점수의 최솟값을 출력한다.
3 2 1 2 3 1 2
2