시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 121 71 59 62.105%

문제

비트 문자열은 0, 1로만 이루어진 문자열이다. 여러분은 비트 문자열을 하나 받아서 특정한 문자열로 바꾸어야 한다. 이때, 여러분이 유일하게 할 수 있는 연산은 인접한 두 비트를 바꾸는 것이다.

초기 문자열의 상태는 그냥 비트의 순열로 주어진다. 하지만 바꾸고자 하는 문자열은 '연속 코드'의 형태로 주어진다. 연속 코드란, 문자열에 나타나는 연속된 0 또는 1의 개수를 차례대로 늘어놓은 순열이다. 예를 들어, "011100"의 연속 코드는 "1 3 2"가 된다. 이때, 여러분도 눈치챘겠지만 연속 코드가 같은 문자열은 0으로 시작하는 것 하나, 그리고 1로 시작하는 것 하나로 항상 두 개씩 있다.

초기 문자열에서 나중 문자열로 문자열을 바꾸는데 필요한 최소한의 연산의 수를 계산하여라.

입력

입력의 첫 줄에는 두 정수 N (1 ≤ N ≤ 15)과 M (1 ≤ M ≤ N)이 주어진다. 둘째 줄에는 N개의 비트가 공백을 사이에 두고 주어진다. 이는 초기 문자열을 의미한다. 셋째 줄에는 바꿔야 하는 문자열의 연속 코드가 M개의 정수로 차례대로 주어진다.

바꿔야 하는 연속 코드의 각 숫자는 항상 1보다 크거나 같고, 그 코드를 모두 더하면 N이 되고, 주어진 비트 문자열이 항상 연속 코드가 나타내는 비트 문자열로 변환될 수 있음이 보장된다.

출력

필요한 최소한의 연산 수를 출력한다.

예제 입력 1

6 3
1 0 0 1 0 1
1 3 2

예제 출력 1

1

예제 입력 2

7 2
1 1 1 0 0 0 0
4 3

예제 출력 2

12

예제 입력 3

15 14
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 2

예제 출력 3

7

예제 입력 4

1 1
0
1

예제 출력 4

0

힌트

예제 입력 1에서 비트 문자열 "100101"은 연속 코드가 "1 3 2"인 비트 문자열로 재배열되어야 한다. 즉, "100011"이나 "011100" 둘 중 한 가지 문자열로 재배열되어야 하는 것이다. "011100"으로 문자열을 바꾸기 위해서는 4번의 연산이 필요하지만 "100011"로 바꾸기 위해서는 1번의 연산이면 충분하다. 따라서 이 경우에는 1이 답이다.

W3sicHJvYmxlbV9pZCI6IjEwMzMwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViZTQ0XHVkMmI4IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM3YWNcdWJjMzBcdWM1ZjRcdWQ1NThcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmU0NFx1ZDJiOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgMCwgMVx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NDAgXHViZTQ0XHVkMmI4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWQ1NThcdWIwOTggXHViYzFiXHVjNTQ0XHVjMTFjJm5ic3A7XHVkMmI5XHVjODE1XHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc3NCBcdWM3MjBcdWM3N2NcdWQ1NThcdWFjOGMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNWYwXHVjMGIwXHVjNzQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgXHViZTQ0XHVkMmI4XHViOTdjIFx1YmMxNFx1YWZiOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2QwOFx1YWUzMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjMGMxXHVkMGRjXHViMjk0IFx1YWRmOFx1YjBlNSBcdWJlNDRcdWQyYjhcdWM3NTggXHVjMjFjXHVjNWY0XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YmMxNFx1YWZiOFx1YWNlMFx1Yzc5MCBcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwICYjMzk7XHVjNWYwXHVjMThkIFx1Y2Y1NFx1YjRkYyYjMzk7XHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzVmMFx1YzE4ZCBcdWNmNTRcdWI0ZGNcdWI3ODAsIFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMCBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHVjNWYwXHVjMThkXHViNDFjIDAgXHViNjEwXHViMjk0IDFcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWIyOThcdWM1YjRcdWIxOTNcdWM3NDAgXHVjMjFjXHVjNWY0XHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAmcXVvdDswMTExMDAmcXVvdDtcdWM3NTggXHVjNWYwXHVjMThkIFx1Y2Y1NFx1YjRkY1x1YjI5NCAmcXVvdDsxIDMgMiZxdW90O1x1YWMwMCBcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjNWVjXHViN2VjXHViZDg0XHViM2M0IFx1YjIwOFx1Y2U1OFx1Y2M1OFx1YWNhMFx1YzljMFx1YjljYyBcdWM1ZjBcdWMxOGQgXHVjZjU0XHViNGRjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAmbmJzcDswXHVjNzNjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWFjODMgXHVkNTU4XHViMDk4LCBcdWFkZjhcdWI5YWNcdWFjZTAgMVx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVhYzgzIFx1ZDU1OFx1YjA5OFx1Yjg1YyZuYnNwO1x1ZDU2ZFx1YzBjMSBcdWI0NTAgXHVhYzFjXHVjNTI5IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDA4XHVhZTMwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1YzVkMFx1YzExYyBcdWIwOThcdWM5MTEgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCZuYnNwO1x1YmMxNFx1YWZiOFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCZuYnNwO04gKDEgJmxlOyBOICZsZTsgMTUpXHVhY2ZjJm5ic3A7TSAoMSAmbGU7IE0gJmxlOyBOKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWJlNDRcdWQyYjhcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgXHVjZDA4XHVhZTMwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzE0XHVhZmQ0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjNWYwXHVjMThkIFx1Y2Y1NFx1YjRkY1x1YWMwMCBNXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMTRcdWFmZDRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzVmMFx1YzE4ZCBcdWNmNTRcdWI0ZGNcdWM3NTggXHVhYzAxIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWQ1NmRcdWMwYzEgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBcdWFkZjggXHVjZjU0XHViNGRjXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWIzNTRcdWQ1NThcdWJhNzQgTlx1Yzc3NCBcdWI0MThcdWFjZTAsIFx1YzhmY1x1YzViNFx1YzljNCBcdWJlNDRcdWQyYjggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1ZDU2ZFx1YzBjMSBcdWM1ZjBcdWMxOGQgXHVjZjU0XHViNGRjXHVhYzAwIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWJlNDRcdWQyYjggXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YmNjMFx1ZDY1OFx1YjQyMCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjXHVkNTVjXHVjNzU4IFx1YzVmMFx1YzBiMCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWMgXHVjNzg1XHViODI1IDFcdWM1ZDBcdWMxMWMgXHViZTQ0XHVkMmI4IFx1YmIzOFx1Yzc5MFx1YzVmNCAmcXVvdDsxMDAxMDEmcXVvdDtcdWM3NDAgXHVjNWYwXHVjMThkIFx1Y2Y1NFx1YjRkY1x1YWMwMCAmcXVvdDsxIDMgMiZxdW90O1x1Yzc3OCBcdWJlNDRcdWQyYjggXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YzdhY1x1YmMzMFx1YzVmNFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgJnF1b3Q7MTAwMDExJnF1b3Q7XHVjNzc0XHViMDk4ICZxdW90OzAxMTEwMCZxdW90OyBcdWI0NTggXHVjOTExIFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YzdhY1x1YmMzMFx1YzVmNFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiAmcXVvdDswMTExMDAmcXVvdDtcdWM3M2NcdWI4NWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YmMxNFx1YWZiOFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgNFx1YmM4OFx1Yzc1OCBcdWM1ZjBcdWMwYjBcdWM3NzQgXHVkNTQ0XHVjNjk0XHVkNTU4XHVjOWMwXHViOWNjICZxdW90OzEwMDAxMSZxdW90O1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IDFcdWJjODhcdWM3NTggXHVjNWYwXHVjMGIwXHVjNzc0XHViYTc0IFx1Y2RhOVx1YmQ4NFx1ZDU1OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMVx1Yzc3NCBcdWIyZjVcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDMzMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJpdCBTdHJpbmcgUmVvcmRlcmluZyIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGhhdmUgdG8gcmVvcmRlciBhIGdpdmVuIGJpdCBzdHJpbmcgYXMgc3BlY2lmaWVkLiBUaGUgb25seSBvcGVyYXRpb24gYWxsb3dlZCBpcyBzd2FwcGluZyBhZGphY2VudCBiaXQgcGFpcnMuIFBsZWFzZSB3cml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzd2FwcyByZXF1aXJlZC48XC9wPlxyXG5cclxuPHA+VGhlIGluaXRpYWwgYml0IHN0cmluZyBpcyBzaW1wbHkgcmVwcmVzZW50ZWQgYnkgYSBzZXF1ZW5jZSBvZiBiaXRzLCB3aGlsZSB0aGUgdGFyZ2V0IGlzIHNwZWNpZmllZCBieSBhIHJ1bi1sZW5ndGggY29kZS4gVGhlIHJ1bi1sZW5ndGggY29kZSBvZiBhIGJpdCBzdHJpbmcgaXMgYSBzZXF1ZW5jZSBvZiB0aGUgbGVuZ3RocyBvZiBtYXhpbWFsIGNvbnNlY3V0aXZlIHNlcXVlbmNlcyBvZiB6ZXJvcyBvciBvbmVzIGluIHRoZSBiaXQgc3RyaW5nLiBGb3IgZXhhbXBsZSwgdGhlIHJ1bi1sZW5ndGggY29kZSBvZiAmbGRxdW87MDExMTAwJnJkcXVvOyBpcyAmbGRxdW87MSAzIDImcmRxdW87LiBOb3RlIHRoYXQgdGhlcmUgYXJlIHR3byBkaWZmZXJlbnQgYml0IHN0cmluZ3Mgd2l0aCB0aGUgc2FtZSBydW4tbGVuZ3RoIGNvZGUsIG9uZSBzdGFydGluZyB3aXRoIHplcm8gYW5kIHRoZSBvdGhlciBzdGFydGluZyB3aXRoIG9uZS4gVGhlIHRhcmdldCBpcyBlaXRoZXIgb2YgdGhlc2UgdHdvLjxcL3A+XHJcblxyXG48cD5JbiBTYW1wbGUgSW5wdXQgMSwgYml0IHN0cmluZyAmbGRxdW87MTAwMTAxJnJkcXVvOyBzaG91bGQgYmUgcmVvcmRlcmVkIHNvIHRoYXQgaXRzIHJ1bi1sZW5ndGggY29kZSBpcyAmbGRxdW87MSAzIDImcmRxdW87LCB3aGljaCBtZWFucyBlaXRoZXIgJmxkcXVvOzEwMDAxMSZyZHF1bzsgb3IgJmxkcXVvOzAxMTEwMCZyZHF1bzsuIEF0IGxlYXN0IGZvdXIgc3dhcHMgYXJlIHJlcXVpcmVkIHRvIG9idGFpbiAmbGRxdW87MDExMTAwJnJkcXVvOy4gT24gdGhlIG90aGVyIGhhbmQsIG9ubHkgb25lIHN3YXAgaXMgcmVxdWlyZWQgdG8gbWFrZSAmbGRxdW87MTAwMDExJnJkcXVvOy4gVGh1cywgaW4gdGhpcyBleGFtcGxlLCAxIGlzIHRoZSBhbnN3ZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgdGVzdCBjYXNlLiBUaGUgdGVzdCBjYXNlIGlzIGZvcm1hdHRlZCBhcyBmb2xsb3dzLjxcL3A+XHJcblxyXG48cHJlPlxyXG5OIE1cclxuYjxzdWI+MTxcL3N1Yj4gYjxzdWI+MjxcL3N1Yj4gLi4uIGI8c3ViPk48XC9zdWI+XHJcbnA8c3ViPjE8XC9zdWI+IHA8c3ViPjI8XC9zdWI+IC4uLiBwPHN1Yj5NPFwvc3ViPjxcL3ByZT5cclxuXHJcbjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOICgxICZsZTsgTiAmbGU7IDE1KSBhbmQgTSAoMSAmbGU7IE0gJmxlOyBOKS4gVGhlIHNlY29uZCBsaW5lIHNwZWNpZmllcyB0aGUgaW5pdGlhbCBiaXQgc3RyaW5nIGJ5IE4gaW50ZWdlcnMuIEVhY2ggaW50ZWdlciBiaSBpcyBlaXRoZXIgMCBvciAxLiBUaGUgdGhpcmQgbGluZSBjb250YWlucyB0aGUgcnVuLWxlbmd0aCBjb2RlLCBjb25zaXN0aW5nIG9mIE0gaW50ZWdlcnMuIEludGVnZXJzIHA8c3ViPjE8XC9zdWI+IHRocm91Z2ggcDxzdWI+TTxcL3N1Yj4gcmVwcmVzZW50IHRoZSBsZW5ndGhzIG9mIGNvbnNlY3V0aXZlIHNlcXVlbmNlcyBvZiB6ZXJvcyBvciBvbmVzIGluIHRoZSBiaXQgc3RyaW5nLCBmcm9tIGxlZnQgdG8gcmlnaHQuIEhlcmUsIDEgJmxlOyBwPHN1Yj5qPFwvc3ViPiBmb3IgMSAmbGU7IGogJmxlOyBNIGFuZCAmU2lnbWE7cDxzdWI+ajxcL3N1Yj4gPSBOIGhvbGQuIEl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgaW5pdGlhbCBiaXQgc3RyaW5nIGNhbiBiZSByZW9yZGVyZWQgaW50byBhIGJpdCBzdHJpbmcgd2l0aCBpdHMgcnVuLWxlbmd0aCBjb2RlIHA8c3ViPjE8XC9zdWI+LCAuLi4gLCBwPHN1Yj5NPFwvc3ViPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN3YXBzIHJlcXVpcmVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Asia > Japan > Asia Regional Contest 2014 in Tokyo A번