시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 29 8 5 20.000%

문제

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번을 판매하면 된다.

W3sicHJvYmxlbV9pZCI6IjIwOTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyZjBcdWNmMTMiLCJkZXNjcmlwdGlvbiI6IjxwPk4oMSZsZTtOJmxlOzMwLDAwMClcdWFjMWNcdWM3NTggXHVjODhjXHVjMTFkXHVjNzNjXHViODVjIFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVhZTMwXHVjYzI4XHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVkM2I4XHVjNzU4XHVjMGMxIFx1Yzg4Y1x1YzExZFx1YzVkMCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzBcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Y2NhMFx1YjNjNCBcdWQ2OGNcdWMwYWNcdWM1ZDBcdWMxMWNcdWIyOTQgXHViYTg1XHVjODA4XHVjNzQ0IFx1YjlkZVx1Yzc3NFx1ZDU1OFx1YzVlYyBcdWFkYzBcdWMxMzFcdWQ1NThcdWIyOTQgXHVhYzAwXHVjODcxXHViNGU0XHVjNWQwXHVhYzhjIFx1YWUzMFx1Y2MyOCBcdWQyZjBcdWNmMTNcdWM3NDQgXHVkMzE0XHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHViYjM4XHVjODFjXHViOTdjIFx1YjJlOFx1YzIxY1x1ZDY1NFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIFx1ZDNiOFx1Yzc1OFx1YzBjMSBcdWJhYThcdWI0ZTAgXHVhYzAwXHVjODcxXHViNGU0XHVjNzQwIEwoMSZsZTtMJmxlOzEwMClcdWJhODVcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWFjMDBcdWM4NzFcdWI0ZTRcdWM3NDAgXHViMmU0XHViNGU0IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVjODhjXHVjMTFkXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCBcdWFjMDEgXHVhYzAwXHVjODcxXHViNGU0XHVjNzQwIFx1YWUzMFx1Y2MyOFx1Yzc1OCBcdWQyYjlcdWM4MTUgXHVjODhjXHVjMTFkXHViZDgwXHVkMTMwIFx1YzVmMFx1YjJlY1x1YzU0NCBMXHVhYzFjXHVjNzU4IFx1Yzg4Y1x1YzExZCBcdWQyZjBcdWNmMTNcdWM3NDQgXHVhZDZjXHViOWU0XHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWFkNmNcdWI5ZTRcdWQ1NThcdWIzNTRcdWI3N2NcdWIzYzQgXHVhZTMwXHVjYzI4IFx1ZDJmMFx1Y2YxM1x1Yzc1OCBcdWFjMDBcdWFjYTlcdWM1ZDBcdWIyOTQgXHVjYzI4XHVjNzc0XHVhYzAwIFx1YzVjNlx1YzljMFx1YjljYywgXHVjMTFjXHViZTQ0XHVjMmE0XHVjNWQwIFx1YjljY1x1Yzg3MVx1ZDU1YyBcdWFjZTBcdWFjMWRcdWI0ZTRcdWM3NzQgXHVjZDk0XHVkNmM0XHVjNWQwIFx1YjJlNFx1YzJkYyBcdWFlMzBcdWNjMjhcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTYwIFx1YWMwMFx1YjJhNVx1YzEzMVx1Yzc3NCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM3YTBcdWM3YWNcdWM4MDFcdWM3NzggXHVjNzc0XHVjNzc1XHVjNzc0IDJcdWI5Y2NcdWQwN2MgXHViYzFjXHVjMGRkXHVkNTU4XHViMjk0IFx1YWM4M1x1YzczY1x1Yjg1YyBcdWFjMDRcdWM4ZmNcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFjMDBcdWM4NzFcdWM1ZDBcdWFjOGMgXHVhZTMwXHVjYzI4IFx1ZDJmMFx1Y2YxM1x1Yzc0NCBcdWQzMTRcdWM5YzAgXHViYWJiXHVkNTU4XHViYTc0IFx1YzdhMFx1YzdhY1x1YzgwMVx1Yzc3OCBcdWM3NzRcdWM3NzVcdWM3NzQgXHViYzFjXHVjMGRkXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHVhZTMwXHVjYzI4IFx1ZDJmMFx1Y2YxM1x1Yzc0NCBcdWQzMTRcdWI0MTggXHVjNmQwXHVkNTU4XHViMjk0IFx1Yzc5MFx1YjlhY1x1YWMwMCBcdWM1NDRcdWIyY2MgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzdhMFx1YzdhY1x1YzgwMSBcdWM3NzRcdWM3NzVcdWM3NzQgMVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWFjMDBcdWM4NzFcdWI0ZTRcdWM3NzQgXHVjNmQwXHVkNTU4XHViMjk0IFx1Yzg4Y1x1YzExZFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWIzMDBcdWM3NTggXHVjN2EwXHVjN2FjXHVjODAxIFx1Yzc3NFx1Yzc3NVx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMTM4IFx1YzgxNVx1YzIxOCBOLCBMLCBNKDEgJmxlOyBNICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IE1cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IHooMSAmbGU7IHogJmxlOyBOLUwrMSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgXHVhZGY4IFx1YWMwMFx1Yzg3MVx1Yzc3NCB6XHViYzg4IFx1Yzg4Y1x1YzExZFx1YmQ4MFx1ZDEzMCB6K0wtMVx1YmM4OCBcdWM4OGNcdWMxMWRcdWFlNGNcdWM5YzBcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTU4XHVhZTMwXHViOTdjIFx1YzZkMFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNkNWNcdWIzMDAgXHVjN2EwXHVjN2FjXHVjODAxIFx1Yzc3NFx1Yzc3NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjEsIDMsIDVcdWJjODggXHVhYzAwXHVjODcxXHViNGU0XHVjNWQwXHVhYzhjIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWIzMDBcdWI4NWMgXHVkMzEwXHViOWU0XHVkNTU4XHVhY2UwLCA0XHViYzg4IFx1YWMwMFx1Yzg3MVx1YzVkMFx1YWM4YyAxfjNcdWJjODhcdWM3NDQsIDJcdWJjODggXHVhYzAwXHVjODcxXHVjNWQwXHVhYzhjIDd+OVx1YmM4OFx1Yzc0NCwgNlx1YmM4OCBcdWFjMDBcdWM4NzFcdWM1ZDBcdWFjOGMgMTN+MTVcdWJjODhcdWM3NDQgXHVkMzEwXHViOWU0XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIwOTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaWNrZXQgT2ZmaWNlIiwiZGVzY3JpcHRpb24iOiI8cD5BIHRpY2tldCBvZmZpY2Ugc2VsbHMgdGlja2V0cyBmb3IgY29uY2VydHMuIEluc3RlYWQgb2Ygc2VsbGluZyB0aWNrZXRzIGZvciBzaW5nbGUgc2VhdHMgaXQgc2VsbHMgYnVuY2hlcyBvZiB0aWNrZXRzIGZvciBhIGZpeGVkIG51bWJlciBvZiBjb25zZWN1dGl2ZSBzZWF0cy4gVGhlIG9mZmljZSBoYXMgcmVjZWl2ZWQgYSBncmVhdCBudW1iZXIgb2YgcHVyY2hhc2Ugb3JkZXJzLiBBIHB1cmNoYXNlIG9yZGVyIGZvciBvbmUgYnVuY2ggb2Ygc2VhdHMgc3BlY2lmaWVzIHRoZSBsb3dlc3Qgc2VhdCBudW1iZXIgaW4gdGhlIGJ1bmNoLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgb2ZmaWNlIG1heSBub3QgYmUgYWJsZSB0byBmdWxmaWxsIGFsbCBvZiB0aGUgcHVyY2hhc2Ugb3JkZXJzLiBNb3Jlb3ZlciwgaWYgaXQgb25seSBhbGxvY2F0ZXMgc2VhdHMgZXhhY3RseSBhcyByZXF1ZXN0ZWQgaW4gdGhlIHB1cmNoYXNlIG9yZGVycyB0aGVuIGEgZ3JlYXQgbnVtYmVyIG9mIHNlYXRzIGNvdWxkIHJlbWFpbiBlbXB0eS4gVGhlcmVmb3JlLCB0aGUgb2ZmaWNlIGFwcGxpZXMgdGhlIGZvbGxvd2luZyBhbGxvY2F0aW9uIGFuZCBwcmljaW5nIHN0cmF0ZWd5LiBJZiBhIHB1cmNoYXNlIG9yZGVyIGlzIGFjY2VwdGVkIGFuZCB0aGUgYWxsb2NhdGVkIHNlYXRzIGFyZSBleGFjdGx5IHRob3NlIHRoYXQgYXJlIHJlcXVlc3RlZCB0aGVuIHRoZSBwdXJjaGFzZXIgcGF5cyBmdWxsLXByaWNlICgyIHBldGFrcyBmb3IgdGhlIGJ1bmNoKS4gSWYgYSBwdXJjaGFzZSBvcmRlciBpcyBhY2NlcHRlZCwgYnV0IHRoZSBhbGxvY2F0ZWQgc2VhdHMgZGlmZmVyIGZyb20gdGhlIHJlcXVlc3RlZCBvbmVzIChvbiBhdCBsZWFzdCBvbmUgcG9zaXRpb24pIHRoZW4gdGhlIHB1cmNoYXNlciBwYXlzIGhhbGYtcHJpY2UgKDEgcGV0YWsgZm9yIHRoZSBidW5jaCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBnb2FsIGlzIHRvIG1heGltaXplIHRoZSB0b3RhbCBpbmNvbWUuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgY29tcHV0ZXMgdGhlIG1heGltYWwgaW5jb21lIHRoYXQgY2FuIGJlIGFjaGlldmVkIChTdWJ0YXNrIEEpIGFuZCBhbGxvY2F0ZXMgdGhlIHNlYXRzIHRvIHRoZSBzZWxlY3RlZCBvcmRlcnMgKFN1YnRhc2sgQikgYWNoaWV2aW5nIHRoaXMgaW5jb21lLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIHRleHQgZmlsZSB0aWNrZXQuaW4gY29udGFpbnMgdHdvIGludGVnZXJzLCBNIGFuZCBMLiBNICgxICZsZTsgTSAmbGU7MzAgMDAwKSBpcyB0aGUgbnVtYmVyIG9mIHNlYXRzIGFuZCBMICgxICZsZTsgTCAmbGU7IDEwMCkgaXMgdGhlIG51bWJlciBvZiBjb25zZWN1dGl2ZSBzZWF0cyBpbiBldmVyeSBidW5jaC4gU2VhdHMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBNLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciwgTiAoMSAmbGU7IE4gJmxlOzEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHB1cmNoYXNlIG9yZGVycy4gVGhlIHRoaXJkIGxpbmUgY29udGFpbnMgTiBpbnRlZ2VycywgZGVmaW5pbmcgdGhlIHB1cmNoYXNlIG9yZGVycy4gVGhlIGl0aCBudW1iZXIgaW4gdGhlIGxpbmUsIHogKDEgJmxlOyB6ICZsZTsgTS1MKzEpLCBtZWFucyB0aGF0IHRoZSBpdGggcHVyY2hhc2VyIHJlcXVlc3RzIHRoZSBidW5jaCBvZiBzZWF0cyBzdGFydGluZyBhdCBzZWF0IHogYW5kIGVuZGluZyBhdCBzZWF0IHorTC0xLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSB0ZXh0IGZpbGUgdGlja2V0Lm91dCBjb250YWlucyBhbiBpbnRlZ2VyLCBTLCB0aGUgbWF4aW1hbCBpbmNvbWUgKFN1YnRhc2sgQSkuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyLCBRLCB0aGUgbnVtYmVyIG9mIGFjY2VwdGVkIG9yZGVycy4gVGhlIG5leHQgUSBsaW5lcyBkZXNjcmliZSB0aGUgc2VhdCBhbGxvY2F0aW9ucyAoU3VidGFzayBCKS4gRWFjaCBsaW5lIGNvbnRhaW5zIGEgcGFpciBvZiBpbnRlZ2VycywgeCB5LiBUaGUgcGFpciB4IHkgbWVhbnMgdGhhdCB0aGUgcHVyY2hhc2VyIHggZ2V0cyB0aGUgc2VhdHMgc3RhcnRpbmcgYXQgc2VhdCBudW1iZXIgeS4gVGhlIGxpbmVzIG11c3QgYmUgd3JpdHRlbiBpbiB0aGUgaW5jcmVhc2luZyBvcmRlciBvZiBzZWF0IG51bWJlcnMuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGFyZSBtdWx0aXBsZSBwb3NzaWJpbGl0aWVzLCB5b3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCBvbmx5IG9uZTsgaXQgZG9lcyBub3QgbWF0dGVyIHdoaWNoIG9uZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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