시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 118 68 56 60.870%

문제

비트 문자열은 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이 답이다.

W3sicHJvYmxlbV9pZCI6IjEwMzMwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViZTQ0XHVkMmI4IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM3YWNcdWJjMzBcdWM1ZjRcdWQ1NThcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmU0NFx1ZDJiOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgMCwgMVx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NDAgXHViZTQ0XHVkMmI4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWQ1NThcdWIwOTggXHViYzFiXHVjNTQ0XHVjMTFjJm5ic3A7XHVkMmI5XHVjODE1XHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NzQgXHVjNzIwXHVjNzdjXHVkNTU4XHVhYzhjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc0MCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1YmU0NFx1ZDJiOFx1Yjk3YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkMDhcdWFlMzAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCBcdWFkZjhcdWIwZTUgXHViZTQ0XHVkMmI4XHVjNzU4IFx1YzIxY1x1YzVmNFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWJjMTRcdWFmYjhcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCAmIzM5O1x1YzVmMFx1YzE4ZCBcdWNmNTRcdWI0ZGMmIzM5O1x1Yzc1OCBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1ZjBcdWMxOGQgXHVjZjU0XHViNGRjXHViNzgwLCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM1ZDAgXHViMDk4XHVkMGMwXHViMDk4XHViMjk0IFx1YzVmMFx1YzE4ZFx1YjQxYyAwIFx1YjYxMFx1YjI5NCAxXHVjNzU4IFx1YWMyZlx1YzIxOFx1Yjk3YyBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHViMjk4XHVjNWI0XHViMTkzXHVjNzQwIFx1YzIxY1x1YzVmNFx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgJnF1b3Q7MDExMTAwJnF1b3Q7XHVjNzU4IFx1YzVmMFx1YzE4ZCBcdWNmNTRcdWI0ZGNcdWIyOTQgJnF1b3Q7MSAzIDImcXVvdDtcdWFjMDAgXHViNDFjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM1ZWNcdWI3ZWNcdWJkODRcdWIzYzQgXHViMjA4XHVjZTU4XHVjYzU4XHVhY2EwXHVjOWMwXHViOWNjIFx1YzVmMFx1YzE4ZCBcdWNmNTRcdWI0ZGNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCZuYnNwOzBcdWM3M2NcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YWM4MyBcdWQ1NThcdWIwOTgsIFx1YWRmOFx1YjlhY1x1YWNlMCAxXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWFjODMgXHVkNTU4XHViMDk4XHViODVjJm5ic3A7XHVkNTZkXHVjMGMxIFx1YjQ1MCBcdWFjMWNcdWM1MjkgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkMDhcdWFlMzAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHVjMTFjIFx1YjA5OFx1YzkxMSBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0Jm5ic3A7XHViYzE0XHVhZmI4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHVjNWYwXHVjMGIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4Jm5ic3A7TiAoMSAmbGU7IE4gJmxlOyAxNSlcdWFjZmMmbmJzcDtNICgxICZsZTsgTSAmbGU7IE4pXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YmU0NFx1ZDJiOFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWNkMDhcdWFlMzAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMTRcdWFmZDRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWM1ZjBcdWMxOGQgXHVjZjU0XHViNGRjXHVhYzAwIE1cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMxNFx1YWZkNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNWYwXHVjMThkIFx1Y2Y1NFx1YjRkY1x1Yzc1OCBcdWFjMDEgXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDU2ZFx1YzBjMSAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIFx1YWRmOCBcdWNmNTRcdWI0ZGNcdWI5N2MgXHViYWE4XHViNDUwIFx1YjM1NFx1ZDU1OFx1YmE3NCBOXHVjNzc0IFx1YjQxOFx1YWNlMCwgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmU0NFx1ZDJiOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVkNTZkXHVjMGMxIFx1YzVmMFx1YzE4ZCBcdWNmNTRcdWI0ZGNcdWFjMDAgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmU0NFx1ZDJiOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViY2MwXHVkNjU4XHViNDIwIFx1YzIxOCBcdWM3ODhcdWM3NGNcdWM3NzQgXHViY2Y0XHVjN2E1XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWQ1NWNcdWM3NTggXHVjNWYwXHVjMGIwIFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjUgMVx1YzVkMFx1YzExYyBcdWJlNDRcdWQyYjggXHViYjM4XHVjNzkwXHVjNWY0ICZxdW90OzEwMDEwMSZxdW90O1x1Yzc0MCBcdWM1ZjBcdWMxOGQgXHVjZjU0XHViNGRjXHVhYzAwICZxdW90OzEgMyAyJnF1b3Q7XHVjNzc4IFx1YmU0NFx1ZDJiOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHVjN2FjXHViYzMwXHVjNWY0XHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCAmcXVvdDsxMDAwMTEmcXVvdDtcdWM3NzRcdWIwOTggJnF1b3Q7MDExMTAwJnF1b3Q7IFx1YjQ1OCBcdWM5MTEgXHVkNTVjIFx1YWMwMFx1YzljMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHVjN2FjXHViYzMwXHVjNWY0XHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuICZxdW90OzAxMTEwMCZxdW90O1x1YzczY1x1Yjg1YyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViYzE0XHVhZmI4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCA0XHViYzg4XHVjNzU4IFx1YzVmMFx1YzBiMFx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWM5YzBcdWI5Y2MgJnF1b3Q7MTAwMDExJnF1b3Q7XHViODVjIFx1YmMxNFx1YWZiOFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgMVx1YmM4OFx1Yzc1OCBcdWM1ZjBcdWMwYjBcdWM3NzRcdWJhNzQgXHVjZGE5XHViZDg0XHVkNTU4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAxXHVjNzc0IFx1YjJmNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMzMwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQml0IFN0cmluZyBSZW9yZGVyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgaGF2ZSB0byByZW9yZGVyIGEgZ2l2ZW4gYml0IHN0cmluZyBhcyBzcGVjaWZpZWQuIFRoZSBvbmx5IG9wZXJhdGlvbiBhbGxvd2VkIGlzIHN3YXBwaW5nIGFkamFjZW50IGJpdCBwYWlycy4gUGxlYXNlIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN3YXBzIHJlcXVpcmVkLjxcL3A+XHJcblxyXG48cD5UaGUgaW5pdGlhbCBiaXQgc3RyaW5nIGlzIHNpbXBseSByZXByZXNlbnRlZCBieSBhIHNlcXVlbmNlIG9mIGJpdHMsIHdoaWxlIHRoZSB0YXJnZXQgaXMgc3BlY2lmaWVkIGJ5IGEgcnVuLWxlbmd0aCBjb2RlLiBUaGUgcnVuLWxlbmd0aCBjb2RlIG9mIGEgYml0IHN0cmluZyBpcyBhIHNlcXVlbmNlIG9mIHRoZSBsZW5ndGhzIG9mIG1heGltYWwgY29uc2VjdXRpdmUgc2VxdWVuY2VzIG9mIHplcm9zIG9yIG9uZXMgaW4gdGhlIGJpdCBzdHJpbmcuIEZvciBleGFtcGxlLCB0aGUgcnVuLWxlbmd0aCBjb2RlIG9mICZsZHF1bzswMTExMDAmcmRxdW87IGlzICZsZHF1bzsxIDMgMiZyZHF1bzsuIE5vdGUgdGhhdCB0aGVyZSBhcmUgdHdvIGRpZmZlcmVudCBiaXQgc3RyaW5ncyB3aXRoIHRoZSBzYW1lIHJ1bi1sZW5ndGggY29kZSwgb25lIHN0YXJ0aW5nIHdpdGggemVybyBhbmQgdGhlIG90aGVyIHN0YXJ0aW5nIHdpdGggb25lLiBUaGUgdGFyZ2V0IGlzIGVpdGhlciBvZiB0aGVzZSB0d28uPFwvcD5cclxuXHJcbjxwPkluIFNhbXBsZSBJbnB1dCAxLCBiaXQgc3RyaW5nICZsZHF1bzsxMDAxMDEmcmRxdW87IHNob3VsZCBiZSByZW9yZGVyZWQgc28gdGhhdCBpdHMgcnVuLWxlbmd0aCBjb2RlIGlzICZsZHF1bzsxIDMgMiZyZHF1bzssIHdoaWNoIG1lYW5zIGVpdGhlciAmbGRxdW87MTAwMDExJnJkcXVvOyBvciAmbGRxdW87MDExMTAwJnJkcXVvOy4gQXQgbGVhc3QgZm91ciBzd2FwcyBhcmUgcmVxdWlyZWQgdG8gb2J0YWluICZsZHF1bzswMTExMDAmcmRxdW87LiBPbiB0aGUgb3RoZXIgaGFuZCwgb25seSBvbmUgc3dhcCBpcyByZXF1aXJlZCB0byBtYWtlICZsZHF1bzsxMDAwMTEmcmRxdW87LiBUaHVzLCBpbiB0aGlzIGV4YW1wbGUsIDEgaXMgdGhlIGFuc3dlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIHNpbmdsZSB0ZXN0IGNhc2UuIFRoZSB0ZXN0IGNhc2UgaXMgZm9ybWF0dGVkIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjxwcmU+XHJcbk4gTVxyXG5iPHN1Yj4xPFwvc3ViPiBiPHN1Yj4yPFwvc3ViPiAuLi4gYjxzdWI+TjxcL3N1Yj5cclxucDxzdWI+MTxcL3N1Yj4gcDxzdWI+MjxcL3N1Yj4gLi4uIHA8c3ViPk08XC9zdWI+PFwvcHJlPlxyXG5cclxuPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gKDEgJmxlOyBOICZsZTsgMTUpIGFuZCBNICgxICZsZTsgTSAmbGU7IE4pLiBUaGUgc2Vjb25kIGxpbmUgc3BlY2lmaWVzIHRoZSBpbml0aWFsIGJpdCBzdHJpbmcgYnkgTiBpbnRlZ2Vycy4gRWFjaCBpbnRlZ2VyIGJpIGlzIGVpdGhlciAwIG9yIDEuIFRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIHRoZSBydW4tbGVuZ3RoIGNvZGUsIGNvbnNpc3Rpbmcgb2YgTSBpbnRlZ2Vycy4gSW50ZWdlcnMgcDxzdWI+MTxcL3N1Yj4gdGhyb3VnaCBwPHN1Yj5NPFwvc3ViPiByZXByZXNlbnQgdGhlIGxlbmd0aHMgb2YgY29uc2VjdXRpdmUgc2VxdWVuY2VzIG9mIHplcm9zIG9yIG9uZXMgaW4gdGhlIGJpdCBzdHJpbmcsIGZyb20gbGVmdCB0byByaWdodC4gSGVyZSwgMSAmbGU7IHA8c3ViPmo8XC9zdWI+IGZvciAxICZsZTsgaiAmbGU7IE0gYW5kICZTaWdtYTtwPHN1Yj5qPFwvc3ViPiA9IE4gaG9sZC4gSXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBpbml0aWFsIGJpdCBzdHJpbmcgY2FuIGJlIHJlb3JkZXJlZCBpbnRvIGEgYml0IHN0cmluZyB3aXRoIGl0cyBydW4tbGVuZ3RoIGNvZGUgcDxzdWI+MTxcL3N1Yj4sIC4uLiAsIHA8c3ViPk08XC9zdWI+LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbWluaW11bSBudW1iZXIgb2Ygc3dhcHMgcmVxdWlyZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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