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

문제

수영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 수영이는 가급적 많은 이득을 얻을 수 있도록 보석을 가져가려 한다. 이때, 다음 세 가지의 조건이 만족되어야 한다.

  1. 보석들과 함께 함정이 설치되어 있기 때문에 1번 보석이 놓여있는 곳부터, N번 보석이 놓여 있는 곳까지 순서대로 이동해야 한다. 물론 1번 보석부터 N번 보석까지가 차례로 놓여있다고 가정하며, 보석을 줍다가 도중에 뒤로 돌아갈 수 없는 것이다. 각각의 보석이 놓여 있는 위치에서 수영이는 두 가지 선택을 할 수 있는데, 그 자리에 있는 보석을 줍거나 줍지 않고 그 다음 보석이 놓여 있는 곳으로 이동하게 된다.
  2. 또한 보석들과 함께 경보 장치가 설치되어 있는데, 이 장치는 보석을 한 개 주우면 작동하게 된다. 보석을 한 개 더 줍게 되면 이 경보 장치는 유적을 무너뜨리도록 설계되어 있다. 단, 경보 장치를 속일 수 있는 방법이 있는데, M(1 ≤ M ≤ N)개 이상의 연속적인 보석을 줍게 되면 경보 장치가 인식하지 못하게 된다. 따라서 보석을 줍기 시작하면 그 위치에 있는 보석을 포함하여 M개 이상의 보석을 연속적으로 주워야 하고, 줍기를 멈춘 후에는 다시 줍기 시작할 수 없다. 즉, 보석을 주울 기회는 오직 한 번 뿐이며, 보석을 주울 때에는 연속적으로 M개 이상 주워야 한다.
  3. 주운 보석들의 가치의 합이 크더라도, 보석의 개수가 많다면 무게가 많이 나가서 힘들 수도 있다. 물론, 보석들의 가치의 합이 충분히 크다면 무거움을 감수할 수도 있다. 따라서 수영이는 주운 보석들의 가치의 평균이 최대가 되도록 하려 한다.

보석들의 개수가 매우 많기 때문에, 수영이는 이 문제를 컴퓨터를 이용하여 풀기로 하였다. 보석들에 대한 정보가 주어졌을 때, 위의 조건들을 만족하면서 보석을 주울 때, 가치의 평균의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 각 보석의 가치가 주어진다. 각 보석의 가치는 0 이상 2,000 이하의 정수이다.

출력

첫째 줄에 가치의 평균의 최댓값을 1,000배 한 정수를 출력한다. 반올림 문제가 생길 수 있으므로, 정수 연산을 하여 1,000×(가치의 총 합)/(보석의 개수)을 출력하도록 한다.

예제 입력 1

10 6
6
4
2
10
3
8
5
9
4
1

예제 출력 1

6500
W3sicHJvYmxlbV9pZCI6IjIxMDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWMxMWQgXHVjOTBkXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMThcdWM2MDFcdWM3NzRcdWIyOTQgXHVhY2UwXHViMzAwIFx1YzcyMFx1YzgwMVx1Yzc0NCBcdWQwZDBcdWMwYWNcdWQ1NThcdWIzNTggXHViM2M0XHVjOTExIFx1YmNmNFx1YzExZFx1Yzc0NCBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1YzcyMFx1YzgwMSBcdWMxOGRcdWM1ZDBcdWIyOTQgTigxICZsZTsgTiAmbGU7IDEwMCwwMDApXHVhYzFjXHVjNzU4IFx1YmNmNFx1YzExZFx1YjRlNFx1Yzc3NCBcdWM3N2NcdWI4MmNcdWI4NWMgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmNmNFx1YzExZFx1Yzc1OCBcdWFjMDBcdWNlNThcdWIyOTQgXHViMmU0XHViOTdjIFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMyMThcdWM2MDFcdWM3NzRcdWIyOTQgXHVhYzAwXHVhZTA5XHVjODAxIFx1YjljZVx1Yzc0MCBcdWM3NzRcdWI0ZGRcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViMmU0XHVjNzRjIFx1YzEzOCBcdWFjMDBcdWM5YzBcdWM3NTggXHVjODcwXHVhYzc0XHVjNzc0IFx1YjljY1x1Yzg3MVx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViY2Y0XHVjMTFkXHViNGU0XHVhY2ZjIFx1ZDU2OFx1YWVkOCBcdWQ1NjhcdWM4MTVcdWM3NzQgXHVjMTI0XHVjZTU4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgMVx1YmM4OCBcdWJjZjRcdWMxMWRcdWM3NzQgXHViMTkzXHVjNWVjXHVjNzg4XHViMjk0IFx1YWNmM1x1YmQ4MFx1ZDEzMCwgTlx1YmM4OCBcdWJjZjRcdWMxMWRcdWM3NzQgXHViMTkzXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YmIzY1x1Yjg2MCAxXHViYzg4IFx1YmNmNFx1YzExZFx1YmQ4MFx1ZDEzMCBOXHViYzg4IFx1YmNmNFx1YzExZFx1YWU0Y1x1YzljMFx1YWMwMCBcdWNjMjhcdWI4NDBcdWI4NWMgXHViMTkzXHVjNWVjXHVjNzg4XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1OFx1YmE3MCwgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YzkwZFx1YjJlNFx1YWMwMCBcdWIzYzRcdWM5MTFcdWM1ZDAgXHViNGE0XHViODVjIFx1YjNjY1x1YzU0NFx1YWMwOCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmNmNFx1YzExZFx1Yzc3NCBcdWIxOTNcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzcwNFx1Y2U1OFx1YzVkMFx1YzExYyBcdWMyMThcdWM2MDFcdWM3NzRcdWIyOTQgXHViNDUwIFx1YWMwMFx1YzljMCBcdWMxMjBcdWQwZGRcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWRmOCBcdWM3OTBcdWI5YWNcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmNmNFx1YzExZFx1Yzc0NCBcdWM5MGRcdWFjNzBcdWIwOTggXHVjOTBkXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWFkZjggXHViMmU0XHVjNzRjIFx1YmNmNFx1YzExZFx1Yzc3NCBcdWIxOTNcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YWNmM1x1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI2MTBcdWQ1NWMgXHViY2Y0XHVjMTFkXHViNGU0XHVhY2ZjIFx1ZDU2OFx1YWVkOCBcdWFjYmRcdWJjZjQgXHVjN2E1XHVjZTU4XHVhYzAwIFx1YzEyNFx1Y2U1OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1Yzc3NCBcdWM3YTVcdWNlNThcdWIyOTQgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1ZDU1YyBcdWFjMWMgXHVjOGZjXHVjNmIwXHViYTc0IFx1Yzc5MVx1YjNkOVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YmNmNFx1YzExZFx1Yzc0NCBcdWQ1NWMgXHVhYzFjIFx1YjM1NCBcdWM5MGRcdWFjOGMgXHViNDE4XHViYTc0IFx1Yzc3NCBcdWFjYmRcdWJjZjQgXHVjN2E1XHVjZTU4XHViMjk0IFx1YzcyMFx1YzgwMVx1Yzc0NCBcdWJiMzRcdWIxMDhcdWI3MjhcdWI5YWNcdWIzYzRcdWI4NWQgXHVjMTI0XHVhY2M0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViMmU4LCBcdWFjYmRcdWJjZjQgXHVjN2E1XHVjZTU4XHViOTdjIFx1YzE4ZFx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM3ODhcdWIyOTRcdWIzNzAsIE0oMSAmbGU7IE0gJmxlOyBOKVx1YWMxYyBcdWM3NzRcdWMwYzFcdWM3NTggXHVjNWYwXHVjMThkXHVjODAxXHVjNzc4IFx1YmNmNFx1YzExZFx1Yzc0NCBcdWM5MGRcdWFjOGMgXHViNDE4XHViYTc0IFx1YWNiZFx1YmNmNCBcdWM3YTVcdWNlNThcdWFjMDAgXHVjNzc4XHVjMmRkXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWJjZjRcdWMxMWRcdWM3NDQgXHVjOTBkXHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YmE3NCBcdWFkZjggXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJjZjRcdWMxMWRcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHVjNWVjIE1cdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YmNmNFx1YzExZFx1Yzc0NCBcdWM1ZjBcdWMxOGRcdWM4MDFcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNmNjXHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHVjOTBkXHVhZTMwXHViOTdjIFx1YmE0OFx1Y2Q5OCBcdWQ2YzRcdWM1ZDBcdWIyOTQgXHViMmU0XHVjMmRjIFx1YzkwZFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVjOTg5LCBcdWJjZjRcdWMxMWRcdWM3NDQgXHVjOGZjXHVjNmI4IFx1YWUzMFx1ZDY4Y1x1YjI5NCBcdWM2MjRcdWM5YzEgXHVkNTVjIFx1YmM4OCBcdWJmZDBcdWM3NzRcdWJhNzAsIFx1YmNmNFx1YzExZFx1Yzc0NCBcdWM4ZmNcdWM2YjggXHViNTRjXHVjNWQwXHViMjk0IFx1YzVmMFx1YzE4ZFx1YzgwMVx1YzczY1x1Yjg1YyBNXHVhYzFjIFx1Yzc3NFx1YzBjMSBcdWM4ZmNcdWM2Y2NcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM4ZmNcdWM2YjQgXHViY2Y0XHVjMTFkXHViNGU0XHVjNzU4IFx1YWMwMFx1Y2U1OFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVkMDZjXHViMzU0XHViNzdjXHViM2M0LCBcdWJjZjRcdWMxMWRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YjljZVx1YjJlNFx1YmE3NCBcdWJiMzRcdWFjOGNcdWFjMDAgXHViOWNlXHVjNzc0IFx1YjA5OFx1YWMwMFx1YzExYyBcdWQ3OThcdWI0ZTQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHViYjNjXHViODYwLCBcdWJjZjRcdWMxMWRcdWI0ZTRcdWM3NTggXHVhYzAwXHVjZTU4XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWNkYTlcdWJkODRcdWQ3ODggXHVkMDZjXHViMmU0XHViYTc0IFx1YmIzNFx1YWM3MFx1YzZjMFx1Yzc0NCBcdWFjMTBcdWMyMThcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YzIxOFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM4ZmNcdWM2YjQgXHViY2Y0XHVjMTFkXHViNGU0XHVjNzU4IFx1YWMwMFx1Y2U1OFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YmNmNFx1YzExZFx1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHViOWU0XHVjNmIwIFx1YjljZVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzIxOFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM3NzQgXHViYjM4XHVjODFjXHViOTdjIFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVkNDgwXHVhZTMwXHViODVjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHViY2Y0XHVjMTFkXHViNGU0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1YjRlNFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWJhNzRcdWMxMWMgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YzhmY1x1YzZiOCBcdWI1NGMsIFx1YWMwMFx1Y2U1OFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IE4sIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjYzI4XHViODQwXHViODVjIFx1YWMwMSBcdWJjZjRcdWMxMWRcdWM3NTggXHVhYzAwXHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmNmNFx1YzExZFx1Yzc1OCBcdWFjMDBcdWNlNThcdWIyOTQgMCBcdWM3NzRcdWMwYzEgMiwwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMFx1Y2U1OFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IDEsMDAwXHViYzMwIFx1ZDU1YyBcdWM4MTVcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJjMThcdWM2MmNcdWI5YmMgXHViYjM4XHVjODFjXHVhYzAwIFx1YzBkZFx1YWUzOCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYmMwXHViODVjLCBcdWM4MTVcdWMyMTggXHVjNWYwXHVjMGIwXHVjNzQ0IFx1ZDU1OFx1YzVlYyAxLDAwMCZ0aW1lczsoXHVhYzAwXHVjZTU4XHVjNzU4IFx1Y2QxZCBcdWQ1NjkpXC8oXHViY2Y0XHVjMTFkXHVjNzU4IFx1YWMxY1x1YzIxOClcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViM2M0XHViODVkIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMTAyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmVzdCBDb3cgRmVuY2VzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiYjMzk7cyBmYXJtIGNvbnNpc3RzIG9mIGEgbG9uZyByb3cgb2YgTiAoMSAmbHQ7PSBOICZsdDs9IDEwMCwwMDApIGZpZWxkcy4gJm5ic3A7RWFjaCBmaWVsZCBjb250YWlucyBhIGNlcnRhaW4gbnVtYmVyIG9mIGNvd3MsIDEgJmx0Oz0gbmNvd3MgJmx0Oz0gMjAwMC48XC9wPlxyXG5cclxuPHA+Rkogd2FudHMgdG8gYnVpbGQgYSBmZW5jZSBhcm91bmQgYSBjb250aWd1b3VzIGdyb3VwIG9mIHRoZXNlIGZpZWxkcyBpbiBvcmRlciB0byBtYXhpbWl6ZSB0aGUgYXZlcmFnZSBudW1iZXIgb2YgY293cyBwZXIgZmllbGQgd2l0aGluIHRoYXQgYmxvY2suIFRoZSBibG9jayBtdXN0IGNvbnRhaW4gYXQgbGVhc3QgRiAoMSAmbHQ7PSBGICZsdDs9IE4pIGZpZWxkcywgd2hlcmUgRiBnaXZlbiBhcyBpbnB1dC48XC9wPlxyXG5cclxuPHA+Q2FsY3VsYXRlIHRoZSBmZW5jZSBwbGFjZW1lbnQgdGhhdCBtYXhpbWl6ZXMgdGhlIGF2ZXJhZ2UsIGdpdmVuIHRoZSBjb25zdHJhaW50LjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIE4gYW5kIEYuPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogRWFjaCBsaW5lIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIsIHRoZSBudW1iZXIgb2YgY293cyBpbiBhIGZpZWxkLiBMaW5lIDIgZ2l2ZXMgdGhlIG51bWJlciBvZiBjb3dzIGluIGZpZWxkIDEsIGxpbmUgMyBnaXZlcyB0aGUgbnVtYmVyIGluIGZpZWxkIDIsIGFuZCBzbyBvbi48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgMTAwMCB0aW1lcyB0aGUgbWF4aW1hbCBhdmVyYWdlLiBEbyBub3QgcGVyZm9ybSByb3VuZGluZywganVzdCBwcmludCB0aGUgaW50ZWdlciB0aGF0IGlzIDEwMDAqbmNvd3NcL25maWVsZHMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO March 2003 Contest > Green 2번

  • 데이터를 추가한 사람: cgiosy
  • 문제의 오타를 찾은 사람: swh98