시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB39019016450.932%

문제

$N$ 개의 숫자 $0$ 과 $M$ 개의 숫자 $1$ 로 이루어진 길이의 $N+M$ 의 두 문자열 ST 가 있다. 이 문자열을 가지고 두 곰곰이 친구가 서로 재미있게 놀다가 갑자기 한 곰곰이가 선을 넘어버렸다.

“선 넘지마”

라는 선언과 함께 문자열 ST 가 선을 사이에 두고 분리되어 버렸다. 곰곰이는 이제 노는 것을 그만두고 문자열을 정리하기로 했다. 하지만 선을 넘을 수 없기 때문에 S 문자열 앞에 앉은 곰곰이는 S 문자열만, T 문자열 앞에 앉은 곰곰이는 T 문자열만 수정할 수 있다.

곰곰이는 문자열에서 임의의 인접한 두 문자의 위치를 바꿀 수 있다. 문자의 위치를 바꾸는 연산을 $X$ 번 수행하면 $X^2$ 만큼의 비용이 든다.

두 곰곰이는 각각 S 문자열에서 $X$ 번, T 문자열에서 $Y$ 번의 연산을 수행하여, ST 가 같은 문자열이 되도록 만들고 싶다. 이 때, 두 곰곰이가 사용한 비용의 합의 최솟값, 즉 $X^2 + Y^2$ 값의 최솟값을 구해보자.

입력

첫째 줄에는 음이 아닌 정수 $N$, $M$ 이 공백을 사이에 두고 주어진다. ($1 \le N + M \le 100\,000$)

이어 두 번째 줄과 세 번째 줄에 각각 문자열 ST 가 주어진다.

문자열 ST 의 길이는 $N+M$ 이며, $N$ 개의 숫자 $0$ 과 $M$ 개의 숫자 $1$ 로 이루어져 있다.

출력

가능한 $X^2 + Y^2$ 의 최소값을 출력한다.

예제 입력 1

4 3
1100100
0100011

예제 출력 1

25

0101010 으로 만들면 최소가 된다.

예제 입력 2

3 0
000
000

예제 출력 2

0

예제 입력 3

2 2
1100
0011

예제 출력 3

8

1001, 0110 둘 다 가능한 모습이다. 1010 으로 만드는 경우, S 는 1번, T 는 3번의 연산을 수행해서 총 1+9=10 의 비용이 소모된다.

출처

Contest > BOJ User Contest > 곰곰컵 > 제2회 곰곰컵 H번