시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB137241314.773%

문제

N(1 ≤ N ≤ 30,000)개의 좌석으로 되어 있는 기차가 있다. 편의상 좌석에 1번부터 N번까지의 번호가 붙어있다고 하자. 철도 회사에서는 명절을 맞이하여 귀성하는 가족들에게 기차 티켓을 팔기로 하였다. 문제를 단순화하기 위해서, 편의상 모든 가족들은 L(1 ≤ L ≤ 100)명으로 이루어져 있다고 가정하자.

각 가족들은 다들 자신이 원하는 좌석이 있다. 즉, 각 가족들은 기차의 특정 좌석부터 연달아 L개의 좌석 티켓을 구매하려 한다. 이와 같이 구매하더라도 기차 티켓의 가격에는 차이가 없지만, 서비스에 만족한 고객들이 추후에 다시 기차를 이용할 가능성이 있기 때문에, 잠재적인 이익이 2만큼 발생하는 것으로 간주한다. 만약 가족에게 기차 티켓을 팔지 못하면 잠재적인 이익이 발생하지 않으며, 기차 티켓을 팔되 원하는 자리가 아닌 경우에는 잠재적 이익이 1이 된다.

각 가족들이 원하는 좌석이 주어졌을 때, 최대의 잠재적 이익을 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 N, L, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 정수 z(1 ≤ z ≤ N-L+1)가 주어진다. 이는 그 가족이 z번 좌석부터 z+L-1번 좌석까지를 구매하기를 원한다는 의미이다.

출력

첫째 줄에 최대 잠재적 이익을 출력한다.

예제 입력 1

20 3 7
4 2 10 9 16 15 17

예제 출력 1

9

힌트

1, 3, 5번 가족들에게 원하는 대로 판매하고, 4번 가족에게 1~3번을, 2번 가족에게 7~9번을, 6번 가족에게 13~15번을 판매하면 된다.

W3sicHJvYmxlbV9pZCI6IjIwOTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyZjBcdWNmMTMiLCJkZXNjcmlwdGlvbiI6IjxwPk4oMSAmbGU7IE4gJmxlOyAzMCwwMDApXHVhYzFjXHVjNzU4IFx1Yzg4Y1x1YzExZFx1YzczY1x1Yjg1YyBcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWUzMFx1Y2MyOFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1ZDNiOFx1Yzc1OFx1YzBjMSBcdWM4OGNcdWMxMWRcdWM1ZDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWNjYTBcdWIzYzQgXHVkNjhjXHVjMGFjXHVjNWQwXHVjMTFjXHViMjk0IFx1YmE4NVx1YzgwOFx1Yzc0NCBcdWI5ZGVcdWM3NzRcdWQ1NThcdWM1ZWMgXHVhZGMwXHVjMTMxXHVkNTU4XHViMjk0IFx1YWMwMFx1Yzg3MVx1YjRlNFx1YzVkMFx1YWM4YyBcdWFlMzBcdWNjMjggXHVkMmYwXHVjZjEzXHVjNzQ0IFx1ZDMxNFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWIyZThcdWMyMWNcdWQ2NTRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWQzYjhcdWM3NThcdWMwYzEgXHViYWE4XHViNGUwIFx1YWMwMFx1Yzg3MVx1YjRlNFx1Yzc0MCBMKDEgJmxlOyBMICZsZTsgMTAwKVx1YmE4NVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YWMwMFx1Yzg3MVx1YjRlNFx1Yzc0MCBcdWIyZTRcdWI0ZTQgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWM4OGNcdWMxMWRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM5ODksIFx1YWMwMSBcdWFjMDBcdWM4NzFcdWI0ZTRcdWM3NDAgXHVhZTMwXHVjYzI4XHVjNzU4IFx1ZDJiOVx1YzgxNSBcdWM4OGNcdWMxMWRcdWJkODBcdWQxMzAgXHVjNWYwXHViMmVjXHVjNTQ0IExcdWFjMWNcdWM3NTggXHVjODhjXHVjMTFkIFx1ZDJmMFx1Y2YxM1x1Yzc0NCBcdWFkNmNcdWI5ZTRcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWFlMzBcdWNjMjggXHVkMmYwXHVjZjEzXHVjNzU4IFx1YWMwMFx1YWNhOVx1YzVkMFx1YjI5NCBcdWNjMjhcdWM3NzRcdWFjMDAgXHVjNWM2XHVjOWMwXHViOWNjLCBcdWMxMWNcdWJlNDRcdWMyYTRcdWM1ZDAgXHViOWNjXHVjODcxXHVkNTVjIFx1YWNlMFx1YWMxZFx1YjRlNFx1Yzc3NCBcdWNkOTRcdWQ2YzRcdWM1ZDAgXHViMmU0XHVjMmRjIFx1YWUzMFx1Y2MyOFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NjAgXHVhYzAwXHViMmE1XHVjMTMxXHVjNzc0IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzdhMFx1YzdhY1x1YzgwMVx1Yzc3OCBcdWM3NzRcdWM3NzVcdWM3NzQgMlx1YjljY1x1ZDA3YyBcdWJjMWNcdWMwZGRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjIFx1YWMwNFx1YzhmY1x1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWMwMFx1Yzg3MVx1YzVkMFx1YWM4YyBcdWFlMzBcdWNjMjggXHVkMmYwXHVjZjEzXHVjNzQ0IFx1ZDMxNFx1YzljMCBcdWJhYmJcdWQ1NThcdWJhNzQgXHVjN2EwXHVjN2FjXHVjODAxXHVjNzc4IFx1Yzc3NFx1Yzc3NVx1Yzc3NCBcdWJjMWNcdWMwZGRcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWFlMzBcdWNjMjggXHVkMmYwXHVjZjEzXHVjNzQ0IFx1ZDMxNFx1YjQxOCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVjNzkwXHViOWFjXHVhYzAwIFx1YzU0NFx1YjJjYyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjN2EwXHVjN2FjXHVjODAxIFx1Yzc3NFx1Yzc3NVx1Yzc3NCAxXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YWMwMFx1Yzg3MVx1YjRlNFx1Yzc3NCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVjODhjXHVjMTFkXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1YjMwMFx1Yzc1OCBcdWM3YTBcdWM3YWNcdWM4MDEgXHVjNzc0XHVjNzc1XHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMxMzggXHVjODE1XHVjMjE4IE4sIEwsIE0oMSAmbGU7IE0gJmxlOyAxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgTVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggeigxICZsZTsgeiAmbGU7IE4tTCsxKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWFkZjggXHVhYzAwXHVjODcxXHVjNzc0IHpcdWJjODggXHVjODhjXHVjMTFkXHViZDgwXHVkMTMwIHorTC0xXHViYzg4IFx1Yzg4Y1x1YzExZFx1YWU0Y1x1YzljMFx1Yjk3YyBcdWFkNmNcdWI5ZTRcdWQ1NThcdWFlMzBcdWI5N2MgXHVjNmQwXHVkNTVjXHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YjMwMCBcdWM3YTBcdWM3YWNcdWM4MDEgXHVjNzc0XHVjNzc1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+MSwgMywgNVx1YmM4OCBcdWFjMDBcdWM4NzFcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjNmQwXHVkNTU4XHViMjk0IFx1YjMwMFx1Yjg1YyBcdWQzMTBcdWI5ZTRcdWQ1NThcdWFjZTAsIDRcdWJjODggXHVhYzAwXHVjODcxXHVjNWQwXHVhYzhjIDF+M1x1YmM4OFx1Yzc0NCwgMlx1YmM4OCBcdWFjMDBcdWM4NzFcdWM1ZDBcdWFjOGMgN345XHViYzg4XHVjNzQ0LCA2XHViYzg4IFx1YWMwMFx1Yzg3MVx1YzVkMFx1YWM4YyAxM34xNVx1YmM4OFx1Yzc0NCBcdWQzMTBcdWI5ZTRcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjA5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRpY2tldCBPZmZpY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkEgdGlja2V0IG9mZmljZSBzZWxscyB0aWNrZXRzIGZvciBjb25jZXJ0cy4gSW5zdGVhZCBvZiBzZWxsaW5nIHRpY2tldHMgZm9yIHNpbmdsZSBzZWF0cyBpdCBzZWxscyBidW5jaGVzIG9mIHRpY2tldHMgZm9yIGEgZml4ZWQgbnVtYmVyIG9mIGNvbnNlY3V0aXZlIHNlYXRzLiBUaGUgb2ZmaWNlIGhhcyByZWNlaXZlZCBhIGdyZWF0IG51bWJlciBvZiBwdXJjaGFzZSBvcmRlcnMuIEEgcHVyY2hhc2Ugb3JkZXIgZm9yIG9uZSBidW5jaCBvZiBzZWF0cyBzcGVjaWZpZXMgdGhlIGxvd2VzdCBzZWF0IG51bWJlciBpbiB0aGUgYnVuY2guJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBvZmZpY2UgbWF5IG5vdCBiZSBhYmxlIHRvIGZ1bGZpbGwgYWxsIG9mIHRoZSBwdXJjaGFzZSBvcmRlcnMuIE1vcmVvdmVyLCBpZiBpdCBvbmx5IGFsbG9jYXRlcyBzZWF0cyBleGFjdGx5IGFzIHJlcXVlc3RlZCBpbiB0aGUgcHVyY2hhc2Ugb3JkZXJzIHRoZW4gYSBncmVhdCBudW1iZXIgb2Ygc2VhdHMgY291bGQgcmVtYWluIGVtcHR5LiBUaGVyZWZvcmUsIHRoZSBvZmZpY2UgYXBwbGllcyB0aGUgZm9sbG93aW5nIGFsbG9jYXRpb24gYW5kIHByaWNpbmcgc3RyYXRlZ3kuIElmIGEgcHVyY2hhc2Ugb3JkZXIgaXMgYWNjZXB0ZWQgYW5kIHRoZSBhbGxvY2F0ZWQgc2VhdHMgYXJlIGV4YWN0bHkgdGhvc2UgdGhhdCBhcmUgcmVxdWVzdGVkIHRoZW4gdGhlIHB1cmNoYXNlciBwYXlzIGZ1bGwtcHJpY2UgKDIgcGV0YWtzIGZvciB0aGUgYnVuY2gpLiBJZiBhIHB1cmNoYXNlIG9yZGVyIGlzIGFjY2VwdGVkLCBidXQgdGhlIGFsbG9jYXRlZCBzZWF0cyBkaWZmZXIgZnJvbSB0aGUgcmVxdWVzdGVkIG9uZXMgKG9uIGF0IGxlYXN0IG9uZSBwb3NpdGlvbikgdGhlbiB0aGUgcHVyY2hhc2VyIHBheXMgaGFsZi1wcmljZSAoMSBwZXRhayBmb3IgdGhlIGJ1bmNoKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGdvYWwgaXMgdG8gbWF4aW1pemUgdGhlIHRvdGFsIGluY29tZS48XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBjb21wdXRlcyB0aGUgbWF4aW1hbCBpbmNvbWUgdGhhdCBjYW4gYmUgYWNoaWV2ZWQgKFN1YnRhc2sgQSkgYW5kIGFsbG9jYXRlcyB0aGUgc2VhdHMgdG8gdGhlIHNlbGVjdGVkIG9yZGVycyAoU3VidGFzayBCKSBhY2hpZXZpbmcgdGhpcyBpbmNvbWUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgdGV4dCBmaWxlIHRpY2tldC5pbiBjb250YWlucyB0aHJlZSBpbnRlZ2VycywgTSwgTCwgYW5kIE4uIE0gKDEgJmxlOyBNICZsZTszMCAwMDApIGlzIHRoZSBudW1iZXIgb2Ygc2VhdHMgYW5kIEwgKDEgJmxlOyBMICZsZTsgMTAwKSBpcyB0aGUgbnVtYmVyIG9mIGNvbnNlY3V0aXZlIHNlYXRzIGluIGV2ZXJ5IGJ1bmNoLiBTZWF0cyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIE0uIE4gKDEgJmxlOyBOICZsZTsxMDAgMDAwKSBpcyB0aGUgbnVtYmVyIG9mIHB1cmNoYXNlIG9yZGVycy4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMsIGRlZmluaW5nIHRoZSBwdXJjaGFzZSBvcmRlcnMuIFRoZSBpdGggbnVtYmVyIGluIHRoZSBsaW5lLCB6ICgxICZsZTsgeiAmbGU7IE0tTCsxKSwgbWVhbnMgdGhhdCB0aGUgaXRoIHB1cmNoYXNlciByZXF1ZXN0cyB0aGUgYnVuY2ggb2Ygc2VhdHMgc3RhcnRpbmcgYXQgc2VhdCB6IGFuZCBlbmRpbmcgYXQgc2VhdCB6K0wtMS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgdGV4dCBmaWxlIHRpY2tldC5vdXQgY29udGFpbnMgYW4gaW50ZWdlciwgUywgdGhlIG1heGltYWwgaW5jb21lIChTdWJ0YXNrIEEpLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciwgUSwgdGhlIG51bWJlciBvZiBhY2NlcHRlZCBvcmRlcnMuIFRoZSBuZXh0IFEgbGluZXMgZGVzY3JpYmUgdGhlIHNlYXQgYWxsb2NhdGlvbnMgKFN1YnRhc2sgQikuIEVhY2ggbGluZSBjb250YWlucyBhIHBhaXIgb2YgaW50ZWdlcnMsIHggeS4gVGhlIHBhaXIgeCB5IG1lYW5zIHRoYXQgdGhlIHB1cmNoYXNlciB4IGdldHMgdGhlIHNlYXRzIHN0YXJ0aW5nIGF0IHNlYXQgbnVtYmVyIHkuIFRoZSBsaW5lcyBtdXN0IGJlIHdyaXR0ZW4gaW4gdGhlIGluY3JlYXNpbmcgb3JkZXIgb2Ygc2VhdCBudW1iZXJzLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBhcmUgbXVsdGlwbGUgcG9zc2liaWxpdGllcywgeW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgb25seSBvbmU7IGl0IGRvZXMgbm90IG1hdHRlciB3aGljaCBvbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Central European Olympiad in Informatics > CEOI 2005 > Day 2 6번

  • 문제의 오타를 찾은 사람: tjdwo5313