시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 155 60 44 41.121%

문제

윤형이와 동혁이가 블록 쌓기 놀이를 한다. 두 명 모두 너비 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

힌트

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

W3sicHJvYmxlbV9pZCI6Ijk5OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlMTRcdWI4NWQgXHVjMzEzXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MjRcdWQ2MTVcdWM3NzRcdWM2NDAgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YmUxNFx1Yjg1ZCBcdWMzMTNcdWFlMzAgXHViMTgwXHVjNzc0XHViOTdjIFx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YmE4NSBcdWJhYThcdWI0NTAgXHViMTA4XHViZTQ0IE5cdWM3NTggXHViZTE0XHViODVkIFx1YWM3NFx1YmIzY1x1Yzc0NCBcdWMzMTNcdWM1NThcdWIyOTRcdWIzNzAsIFx1YzcyNFx1ZDYxNVx1Yzc3NFx1YjI5NCBrXHViYzg4XHVjOWY4IFx1YzVmNFx1YzVkMCBZPHN1Yj5rPFwvc3ViPlx1YWMxY1x1Yzc1OCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjMzEzXHVjNTU4XHVhY2UwIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBrXHViYzg4XHVjOWY4IFx1YzVmNFx1YzVkMCBEPHN1Yj5rPFwvc3ViPlx1YWMxY1x1Yzc1OCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVjMzEzXHVjNTU4XHViMmU0LiBcdWM3MjRcdWQ2MTVcdWM3NzRcdWM2NDAgXHViM2Q5XHVkNjAxXHVjNzc0XHViMjk0IFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWMzMTNcdWFjNzBcdWIwOTggXHViZTdjXHViYTc0XHVjMTFjIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViNjExXHVhYzE5XHVjNzQwIFx1YWM3NFx1YmIzY1x1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC91cGxvYWRcL2ltYWdlc1wva29ja2ljZS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjVweDsgbGluZS1oZWlnaHQ6MjAuOHB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6NDI1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkNTVjXHVkM2I4LCBcdWM3NzQgXHViNDU4XHVjNzc0IFx1YzBjOFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWIyOTQgXHVhYzc0XHViYjNjXHVjNzQwIFx1YzcwNCBcdWFkZjhcdWI5YmNcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkIFx1ZDYxNVx1ZDBkY1x1YzY0MCBcdWFjMTlcdWM3NzQgXHVkMzI5XHViOWU4IFx1YmFhOFx1YzU5MVx1Yzc3NCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVhYzA4XHVjMjE4XHViODVkIFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzEwXHVjMThjXHVkNTU4XHViMmU0XHVhYzAwIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWFmMzRcdWM3NzQgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViNDUwIFx1YzVmNFx1Yzc1OCBcdWJlMTRcdWI4NWRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWQ1NWMgXHVhYzFjXHVjNTI5XHViOWNjIFx1Y2MyOFx1Yzc3NFx1YjA5OFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1YmUxNFx1Yjg1ZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWM1ZjRcdWM3NDAgXHVjODE1XHVjOTExXHVjNTU5XHVjNzc0XHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzI5XHVjNzQ0IFx1YzViNFx1YzljMFx1Yjk3NFx1YzljMCBcdWM1NGFcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWJlMTRcdWI4NWRcdWM3NDQgXHVkNTU4XHViMDk4IFx1YmU5MFx1YzczY1x1YmE3NCBcdWJjMTRcdWI4NWMgXHViZTE0XHViODVkIFx1YzBjMVx1Yzc5MFx1YzVkMCBcdWIxMjNcdWIyOTRcdWIyZTQuIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWIyZTRcdWI5NzggXHVhY2YzXHVjNzNjXHViODVjIFx1YzYyZVx1YWNhOFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWMwYzFcdWM3OTBcdWM1ZDAgXHViMTIzXHVjNWM4XHViMmU0XHVhYzAwIFx1YmU3Y1x1YzExYyBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVhY2YzXHVjNWQwIFx1YzMxM1x1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcyNFx1ZDYxNVx1Yzc3NFx1YzY0MCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjNmQwXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWJlMTRcdWI4NWQgXHVhYzc0XHViYjNjXHVjNzQ0IFx1YmMxNFx1YWZjMCBcdWI1NGMsIFx1YmUxNFx1Yjg1ZFx1Yzc0NCBcdWJlN2NcdWFjNzBcdWIwOTggXHVjMzEzXHViMjk0IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWQ2NTRcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWJlMTRcdWI4NWQgXHVhYzc0XHViYjNjXHVjNzU4IFx1YjEwOFx1YmU0NCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCBcdWQ2NDBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzcyNFx1ZDYxNVx1Yzc3NFx1Yzc1OCBcdWJlMTRcdWI4NWQgXHVhYzc0XHViYjNjXHVjNzU4IFx1YjE5Mlx1Yzc3NCBZPHN1Yj5rPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNkOVx1ZDYwMVx1Yzc3NFx1Yzc1OCBcdWJlMTRcdWI4NWQgXHVhYzc0XHViYjNjXHVjNzU4IFx1YjE5Mlx1Yzc3NCBEPHN1Yj5rPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViZTE0XHViODVkXHVjNzQ0IFx1YzMxM1x1YWM3MFx1YjA5OCBcdWJlN2NcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzU4IFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM3MjRcdWQ2MTVcdWM3NzRcdWM3NTggXHViZTE0XHViODVkIFx1YWM3NFx1YmIzY1x1Yzc1OCAxXHViYzg4XHVjOWY4IFx1YzVmNFx1YzVkMCBcdWJlMTRcdWI4NWQgMlx1YWMxY1x1Yjk3YyBcdWIzNTQgXHVjMzEzXHVhY2UwLCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWM3NTggXHViZTE0XHViODVkIFx1YWM3NFx1YmIzY1x1Yzc1OCAzXHViYzg4XHVjOWY4IFx1YzVmNFx1YzVkMCBcdWJlMTRcdWI4NWQgMVx1YWMxY1x1Yjk3YyBcdWIzNTQgXHVjMzEzXHVjNzNjXHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDMwMCwwMDA8XC9saT5cclxuXHQ8bGk+MCAmbGU7IFk8c3ViPms8XC9zdWI+LCBEPHN1Yj5rPFwvc3ViPiAmbGU7IDEwPHN1cD4xMjxcL3N1cD48XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6Ijk5OTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLT0NLSUNFIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIGFyZSBwbGF5aW5nIHdpdGggYnJpY2tzLiBCb3RoIG9mIHRoZW0gaGF2ZSB0aGVpciBvd24gcGlsZSBvZiBicmlja3MuIFRoZSBwaWxlcyBjb25zaXN0IG9mIE4gY29sdW1ucyAod2hlcmUgTiBpcyBhbiBvZGQgbnVtYmVyKS4gVGhlIG51bWJlciBvZiBicmlja3MgaW4gdGhlIGk8c3VwPnRoPFwvc3VwPiBjb2x1bW4gb2YgTWlya28mIzM5O3MgcGlsZSBpcyBsYWJlbGVkIHdpdGggbTxzdWI+aTxcL3N1Yj4gYW5kIFNsYXZrbyYjMzk7cyBwaWxlIHdpdGggczxzdWI+aTxcL3N1Yj4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXkgaGF2ZSBkZWNpZGVkIHRvIGNyZWF0ZSB0d28gZXF1YWwgcGlsZXMgY29uc3RydWN0ZWQgaW4gYSB3YXkgdGhhdCB0aGUgaGVpZ2h0cyBvZiBjb2x1bW5zIGFyZSBzdHJpY3RseSBkZXNjZW5kaW5nIGF0IGZpcnN0IGFuZCB0aGVuIHN0cmljdGx5IGFzY2VuZGluZyAoc2VlIHJpZ2h0IGltYWdlIGJlbG93KSBhbmQgdGhlIGhlaWdodHMgb2YgYWRqYWNlbnQgY29sdW1ucyBkaWZmZXIgZXhhY3RseSBieSAxIChzZWUgaW1hZ2UpLiBUaGUgbG93ZXN0IG9mIHRoZSBjb2x1bW5zIG11c3QgaGF2ZSBhbiBlcXVhbG51bWJlciBvZiBjb2x1bW5zIHRvIHRoZSBsZWZ0IGFuZCB0byB0aGUgcmlnaHQgb2YgaXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBwaWxlcyBjYW4gYmUgbW9kaWZpZWQgYnkgcmVtb3Zpbmcgb25lIGJyaWNrIGZyb20gdGhlIHRvcCBvZiBzb21lIGNvbHVtbiBhbmQgdGhyb3cgaXQgb3V0IHRoZSB3aW5kb3cgKHRoZXkgY2Fubm90IHJldXNlIGl0KSBvciBieSB0YWtpbmcgb25lIGJyaWNrIGZyb20gdGhlIGJveCBhbmQgcGxhY2UgaXQgb24gdGhlIHRvcCBvZiBzb21lIGNvbHVtbiAodGhlcmUgaXMgYW4gaW5maW5pdGUgYW1vdW50IG9mIGJyaWNrcyBpbiB0aGUgYm94KS4gUmVtb3Zpbmcgb3IgcGxhY2luZyBhIGJyaWNrIGNvdW50cyBhcyBvbmUgbW92ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IGhhdmUgdG8gZGV0ZXJtaW5lIHRoZSBtaW5pbWFsIG51bWJlciBvZiBtb3ZlcyBzbyB0aGF0IE1pcmtvIGFuZCBTbGF2a28gY2FuIHJlYXJyYW5nZSB0aGVpciBwaWxlcyBpbiB0aGUgZGVzY3JpYmVkIHdheS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9rb2NraWNlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyNXB4OyB3aWR0aDo0MjVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5PbiB0aGUgbGVmdCwgdGhlcmUgaXMgYSBwaWxlIHdpdGggY29sdW1uIGhlaWdodHMgMywgMiwgMCwgMSBhbmQgNC4gT24gdGhlIHJpZ2h0LCB0aGVyZSBpcyBvbmUgb2YgdGhlIHBvc3NpYmxlIGZpbmFsIGxheW91dHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBvZGQgbnVtYmVyIE4uICgxICZsZTsgTiAmbGU7IDMwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgaW4gYm90aCBwaWxlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gaW50ZWdlcnMgbTxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBtPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD4xMjxcL3N1cD4pLCBjb2x1bW4gaGVpZ2h0cyBpbiBNaXJrbyYjMzk7cyBwaWxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIGludGVnZXJzIHM8c3ViPmk8XC9zdWI+ICgwICZsZTsgczxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+MTI8XC9zdXA+KSwgY29sdW1uIGhlaWdodHMgaW4gU2xhdmtvJiMzOTtzIHBpbGUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbWluaW1hbCBudW1iZXIgb2YgbW92ZXMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPk1pcmtvIHBsYWNlcyB0d28gYnJpY2tzIG9uIHRoZSB0b3AgdGhlIGZpcnN0IGNvbHVtbiBpbiBoaXMgcGlsZSBhbmQgU2xhdmtvIHBsYWNlcyBvbmUgYnJpY2sgb24gdGhlIHRvcCBvZiB0aGUgdGhpcmQgY29sdW1uIGluIGhpcyBwaWxlLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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