시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB84723017128.500%

문제

윤형이와 동혁이가 블록 쌓기 놀이를 한다. 두 명 모두 너비 N의 블록 건물을 쌓았는데, 윤형이는 k번째 열에 Yk개의 블록을 쌓았고 동혁이는 k번째 열에 Dk개의 블록을 쌓았다. 윤형이와 동혁이는 블록을 쌓거나 빼면서 두 개의 똑같은 건물을 만들려고 한다.

한편, 이 둘이 새로 만들려는 건물은 위 그림의 오른쪽 형태와 같이 팩맨 모양이 되어야 한다. 즉, 왼쪽에서 오른쪽으로 갈수록 블록의 개수가 감소하다가 증가하는 꼴이 되어야 한다. 또, 인접한 두 열의 블록의 개수는 정확히 한 개씩만 차이나야 하며, 블록의 개수가 가장 적은 열은 정중앙이여야 한다.

방을 어지르지 않기 위해서, 블록을 하나 뺐으면 바로 블록 상자에 넣는다. 블록을 다른 곳으로 옮겨야 한다면, 블록을 상자에 넣었다가 빼서 원하는 곳에 쌓아야 한다. 블록 상자에는 무한히 많은 블록이 있다.

윤형이와 동혁이가 원하는 방법으로 블록 건물을 바꿀 때, 블록을 빼거나 쌓는 횟수를 최소화하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 두 블록 건물의 너비 N이 주어진다. N은 홀수이다.

두 번째 줄에는 윤형이의 블록 건물의 높이 Yk가 주어진다.

세 번째 줄에는 동혁이의 블록 건물의 높이 Dk가 주어진다.

출력

블록을 쌓거나 빼는 작업의 수의 최솟값을 출력한다.

제한

  • 1 ≤ N ≤ 300,000
  • 0 ≤ Yk, Dk ≤ 1012

예제 입력 1

3
1 2 3
3 2 2

예제 출력 1

3

예제 입력 2

5
2 3 0 1 4
3 3 2 3 1

예제 출력 2

10

힌트

첫 번째 예제의 경우 윤형이의 블록 건물의 1번째 열에 블록 2개를 더 쌓고, 동혁이의 블록 건물의 3번째 열에 블록 1개를 더 쌓으면 된다.

W3sicHJvYmxlbV9pZCI6Ijk5OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlMTRcdWI4NWQgXHVjMzEzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MjRcdWQ2MTVcdWM3NzRcdWM2NDAgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YmUxNFx1Yjg1ZCBcdWMzMTNcdWFlMzAgXHViMTgwXHVjNzc0XHViOTdjIFx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YmE4NSBcdWJhYThcdWI0NTAgXHViMTA4XHViZTQ0IE5cdWM3NTggXHViZTE0XHViODVkIFx1YWM3NFx1YmIzY1x1Yzc0NCBcdWMzMTNcdWM1NThcdWIyOTRcdWIzNzAsIFx1YzcyNFx1ZDYxNVx1Yzc3NFx1YjI5NCBrXHViYzg4XHVjOWY4IFx1YzVmNFx1YzVkMCBZPHN1Yj5rPFwvc3ViPlx1YWMxY1x1Yzc1OCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjMzEzXHVjNTU4XHVhY2UwIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBrXHViYzg4XHVjOWY4IFx1YzVmNFx1YzVkMCBEPHN1Yj5rPFwvc3ViPlx1YWMxY1x1Yzc1OCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjMzEzXHVjNTU4XHViMmU0LiBcdWM3MjRcdWQ2MTVcdWM3NzRcdWM2NDAgXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWMzMTNcdWFjNzBcdWIwOTggXHViZTdjXHViYTc0XHVjMTFjIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViNjExXHVhYzE5XHVjNzQwIFx1YWM3NFx1YmIzY1x1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzg2OTExMDU1LTNjMmYtNGU1MS1iY2U3LTJhMmZkY2I1OTdmM1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzg3cHg7IGhlaWdodDogMTEycHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDU1Y1x1ZDNiOCwgXHVjNzc0IFx1YjQ1OFx1Yzc3NCBcdWMwYzhcdWI4NWMgXHViOWNjXHViNGU0XHViODI0XHViMjk0IFx1YWM3NFx1YmIzY1x1Yzc0MCBcdWM3MDQgXHVhZGY4XHViOWJjXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWQ2MTVcdWQwZGNcdWM2NDAgXHVhYzE5XHVjNzc0IFx1ZDMyOVx1YjllOCBcdWJhYThcdWM1OTFcdWM3NzQgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YWMwOFx1YzIxOFx1Yjg1ZCBcdWJlMTRcdWI4NWRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YjJlNFx1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVhZjM0XHVjNzc0IFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWM1ZjRcdWM3NTggXHViZTE0XHViODVkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHVkNTVjIFx1YWMxY1x1YzUyOVx1YjljYyBcdWNjMjhcdWM3NzRcdWIwOThcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWJlMTRcdWI4NWRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVjNWY0XHVjNzQwIFx1YzgxNVx1YzkxMVx1YzU1OVx1Yzc3NFx1YzVlY1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMyOVx1Yzc0NCBcdWM1YjRcdWM5YzBcdWI5NzRcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHViZTE0XHViODVkXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWJlOTBcdWM3M2NcdWJhNzQgXHViYzE0XHViODVjIFx1YmUxNFx1Yjg1ZCBcdWMwYzFcdWM3OTBcdWM1ZDAgXHViMTIzXHViMjk0XHViMmU0LiBcdWJlMTRcdWI4NWRcdWM3NDQgXHViMmU0XHViOTc4IFx1YWNmM1x1YzczY1x1Yjg1YyBcdWM2MmVcdWFjYThcdWM1N2MgXHVkNTVjXHViMmU0XHViYTc0LCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjMGMxXHVjNzkwXHVjNWQwIFx1YjEyM1x1YzVjOFx1YjJlNFx1YWMwMCBcdWJlN2NcdWMxMWMgXHVjNmQwXHVkNTU4XHViMjk0IFx1YWNmM1x1YzVkMCBcdWMzMTNcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwO1x1YmUxNFx1Yjg1ZCBcdWMwYzFcdWM3OTBcdWM1ZDBcdWIyOTQgXHViYjM0XHVkNTVjXHVkNzg4IFx1YjljZVx1Yzc0MCBcdWJlMTRcdWI4NWRcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjRcdWQ2MTVcdWM3NzRcdWM2NDAgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHViZTE0XHViODVkIFx1YWM3NFx1YmIzY1x1Yzc0NCBcdWJjMTRcdWFmYzAgXHViNTRjLCBcdWJlMTRcdWI4NWRcdWM3NDQgXHViZTdjXHVhYzcwXHViMDk4IFx1YzMxM1x1YjI5NCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHViZTE0XHViODVkIFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWIxMDhcdWJlNDQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVkNjQwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3MjRcdWQ2MTVcdWM3NzRcdWM3NTggXHViZTE0XHViODVkIFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWIxOTJcdWM3NzQgWTxzdWI+azxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWM3NTggXHViZTE0XHViODVkIFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWIxOTJcdWM3NzQgRDxzdWI+azxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWMzMTNcdWFjNzBcdWIwOTggXHViZTdjXHViMjk0IFx1Yzc5MVx1YzVjNVx1Yzc1OCBcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwIFx1YzcyNFx1ZDYxNVx1Yzc3NFx1Yzc1OCBcdWJlMTRcdWI4NWQgXHVhYzc0XHViYjNjXHVjNzU4IDFcdWJjODhcdWM5ZjggXHVjNWY0XHVjNWQwIFx1YmUxNFx1Yjg1ZCAyXHVhYzFjXHViOTdjIFx1YjM1NCBcdWMzMTNcdWFjZTAsIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1Yzc1OCBcdWJlMTRcdWI4NWQgXHVhYzc0XHViYjNjXHVjNzU4IDNcdWJjODhcdWM5ZjggXHVjNWY0XHVjNWQwIFx1YmUxNFx1Yjg1ZCAxXHVhYzFjXHViOTdjIFx1YjM1NCBcdWMzMTNcdWM3M2NcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMzAwLDAwMDxcL2xpPlxyXG5cdDxsaT4wICZsZTsgWTxzdWI+azxcL3N1Yj4sIEQ8c3ViPms8XC9zdWI+ICZsZTsgMTA8c3VwPjEyPFwvc3VwPjxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiOTk5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktPQ0tJQ0UiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGFuZCBTbGF2a28gYXJlIHBsYXlpbmcgd2l0aCBicmlja3MuIEJvdGggb2YgdGhlbSBoYXZlIHRoZWlyIG93biBwaWxlIG9mIGJyaWNrcy4gVGhlIHBpbGVzIGNvbnNpc3Qgb2YgTiBjb2x1bW5zICh3aGVyZSBOIGlzIGFuIG9kZCBudW1iZXIpLiBUaGUgbnVtYmVyIG9mIGJyaWNrcyBpbiB0aGUgaTxzdXA+dGg8XC9zdXA+IGNvbHVtbiBvZiBNaXJrbyYjMzk7cyBwaWxlIGlzIGxhYmVsZWQgd2l0aCBtPHN1Yj5pPFwvc3ViPiBhbmQgU2xhdmtvJiMzOTtzIHBpbGUgd2l0aCBzPHN1Yj5pPFwvc3ViPi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhleSBoYXZlIGRlY2lkZWQgdG8gY3JlYXRlIHR3byBlcXVhbCBwaWxlcyBjb25zdHJ1Y3RlZCBpbiBhIHdheSB0aGF0IHRoZSBoZWlnaHRzIG9mIGNvbHVtbnMgYXJlIHN0cmljdGx5IGRlc2NlbmRpbmcgYXQgZmlyc3QgYW5kIHRoZW4gc3RyaWN0bHkgYXNjZW5kaW5nIChzZWUgcmlnaHQgaW1hZ2UgYmVsb3cpIGFuZCB0aGUgaGVpZ2h0cyBvZiBhZGphY2VudCBjb2x1bW5zIGRpZmZlciBleGFjdGx5IGJ5IDEgKHNlZSBpbWFnZSkuIFRoZSBsb3dlc3Qgb2YgdGhlIGNvbHVtbnMgbXVzdCBoYXZlIGFuIGVxdWFsbnVtYmVyIG9mIGNvbHVtbnMgdG8gdGhlIGxlZnQgYW5kIHRvIHRoZSByaWdodCBvZiBpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHBpbGVzIGNhbiBiZSBtb2RpZmllZCBieSByZW1vdmluZyBvbmUgYnJpY2sgZnJvbSB0aGUgdG9wIG9mIHNvbWUgY29sdW1uIGFuZCB0aHJvdyBpdCBvdXQgdGhlIHdpbmRvdyAodGhleSBjYW5ub3QgcmV1c2UgaXQpIG9yIGJ5IHRha2luZyBvbmUgYnJpY2sgZnJvbSB0aGUgYm94IGFuZCBwbGFjZSBpdCBvbiB0aGUgdG9wIG9mIHNvbWUgY29sdW1uICh0aGVyZSBpcyBhbiBpbmZpbml0ZSBhbW91bnQgb2YgYnJpY2tzIGluIHRoZSBib3gpLiBSZW1vdmluZyBvciBwbGFjaW5nIGEgYnJpY2sgY291bnRzIGFzIG9uZSBtb3ZlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgaGF2ZSB0byBkZXRlcm1pbmUgdGhlIG1pbmltYWwgbnVtYmVyIG9mIG1vdmVzIHNvIHRoYXQgTWlya28gYW5kIFNsYXZrbyBjYW4gcmVhcnJhbmdlIHRoZWlyIHBpbGVzIGluIHRoZSBkZXNjcmliZWQgd2F5LiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzg2OTExMDU1LTNjMmYtNGU1MS1iY2U3LTJhMmZkY2I1OTdmM1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzg3cHg7IGhlaWdodDogMTEycHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPk9uIHRoZSBsZWZ0LCB0aGVyZSBpcyBhIHBpbGUgd2l0aCBjb2x1bW4gaGVpZ2h0cyAzLCAyLCAwLCAxIGFuZCA0LiBPbiB0aGUgcmlnaHQsIHRoZXJlIGlzIG9uZSBvZiB0aGUgcG9zc2libGUgZmluYWwgbGF5b3V0cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIG9kZCBudW1iZXIgTi4gKDEgJmxlOyBOICZsZTsgMzAwIDAwMCksIHRoZSBudW1iZXIgb2YgY29sdW1ucyBpbiBib3RoIHBpbGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBpbnRlZ2VycyBtPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IG08c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjEyPFwvc3VwPiksIGNvbHVtbiBoZWlnaHRzIGluIE1pcmtvJiMzOTtzIHBpbGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gaW50ZWdlcnMgczxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBzPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD4xMjxcL3N1cD4pLCBjb2x1bW4gaGVpZ2h0cyBpbiBTbGF2a28mIzM5O3MgcGlsZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtaW5pbWFsIG51bWJlciBvZiBtb3Zlcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+Q2xhcmlmaWNhdGlvbiBvZiB0aGUgZmlyc3QgZXhhbXBsZTogTWlya28gcGxhY2VzIHR3byBicmlja3Mgb24gdGhlIHRvcCB0aGUgZmlyc3QgY29sdW1uIGluIGhpcyBwaWxlIGFuZCBTbGF2a28gcGxhY2VzIG9uZSBicmljayBvbiB0aGUgdG9wIG9mIHRoZSB0aGlyZCBjb2x1bW4gaW4gaGlzIHBpbGUuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #6 3번