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

문제

농부 존의 식당은 N마리의 소들에게 M개의 음식을 제공해 주고 있다.

소들은 자신들이 선호하는 음식 Pi를 가지고 있는데, 농부 존은 다음 방법으로 소들에게 음식을 공급한다.

  • 들어오는 소들을 순서대로 그룹으로 나눈다. [1 ~ 4] / [5 ~ 7] / [8 ~ 10] 이런 식으로.
  • 그룹에 있는 소들에게 음식을 제공하는 데 드는 비용은 (해당 그룹에서 선호하는 음식의 합집합 크기)^2 이다. 음식을 수로 생각하면, 서로 다른 수들의 개수의 제곱이다.

최소 비용으로 음식을 제공하려면 어떻게 해야 할까?

입력

첫 번째 줄에 N, M이 주어진다. (1 ≤ M ≤ N ≤ 40000)

이후 N개의 줄에 Pi가 주어진다. (1 ≤ Pi ≤ M)

출력

최소 비용을 출력하라.

예제 입력 1

13 4
1
2
1
3
2
2
3
4
3
4
3
1
4

예제 출력 1

11

힌트

[1] [2] [3] [4] [5, 6] [7, 8, 9, 10, 11] [12] [13] 과 같이 묶으면, 1 + 1 + 1 + 1 + 1 + 4 + 1 + 1 = 11의 비용이 든다.

W3sicHJvYmxlbV9pZCI6IjYxMDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZGRcdWIyZjkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjE4ZFx1YmQ4MCBcdWM4NzRcdWM3NTggXHVjMmRkXHViMmY5XHVjNzQwIE5cdWI5YzhcdWI5YWNcdWM3NTggXHVjMThjXHViNGU0XHVjNWQwXHVhYzhjIE1cdWFjMWNcdWM3NTggXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzgxY1x1YWNmNVx1ZDU3NCBcdWM4ZmNcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxOGNcdWI0ZTRcdWM3NDAgXHVjNzkwXHVjMmUwXHViNGU0XHVjNzc0IFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWM3NGNcdWMyZGQgUDxzdWI+aTxcL3N1Yj5cdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHViMThkXHViZDgwIFx1Yzg3NFx1Yzc0MCBcdWIyZTRcdWM3NGMgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YzE4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWM3NGNcdWMyZGRcdWM3NDQgXHVhY2Y1XHVhZTA5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YjRlNFx1YzViNFx1YzYyNFx1YjI5NCBcdWMxOGNcdWI0ZTRcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YWRmOFx1YjhmOVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDhcdWIyZTQuIFsxIH4gNF0gXC8gWzUgfiA3XSBcLyBbOCB+IDEwXSBcdWM3NzRcdWI3ZjAgXHVjMmRkXHVjNzNjXHViODVjLjxcL2xpPlxyXG5cdDxsaT5cdWFkZjhcdWI4ZjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzE4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWM3NGNcdWMyZGRcdWM3NDQgXHVjODFjXHVhY2Y1XHVkNTU4XHViMjk0IFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwIChcdWQ1NzRcdWIyZjkgXHVhZGY4XHViOGY5XHVjNWQwXHVjMTFjIFx1YzEyMFx1ZDYzOFx1ZDU1OFx1YjI5NCBcdWM3NGNcdWMyZGRcdWM3NTggXHVkNTY5XHVjOWQxXHVkNTY5IFx1ZDA2Y1x1YWUzMCleMiBcdWM3NzRcdWIyZTQuIFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWMyMThcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTU4XHViYTc0LCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzIxOFx1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjODFjXHVhY2YxXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3M2NcdWI4NWMgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzgxY1x1YWNmNVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVkNTc0XHVjNTdjIFx1ZDU2MFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIE4sIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7Jm5ic3A7TSAmbGU7IE4gJmxlOyZuYnNwOzQwMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgUDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7Jm5ic3A7UDxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7Jm5ic3A7TSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+WzFdIFsyXSBbM10gWzRdIFs1LCA2XSBbNywgOCwgOSwgMTAsIDExXSBbMTJdIFsxM10gXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWJiMzZcdWM3M2NcdWJhNzQsIDEgKyAxICsgMSArIDEgKyAxICsgNCArIDEgKyAxID0gMTFcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzc0IFx1YjRlMFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjYxMDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDbGVhbmluZyBVcCIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIGdvb2Qgb2xkIGRheXMsIEZhcm1lciBKb2huIHNlcnZlZCBhIGJvcmluZyBjdWlzaW5lIGNvbXByaXNpbmcgYnV0IGEgc2luZ2xlIHR5cGUgb2YgY293IGZvb2QgdG8gaGlzIE4gKDEgJmx0Oz0gTiAmbHQ7PSA0MDAwMCkgcHJpemUgZGFpcnkgY293cy4gVGltZXMgY2hhbmdlLiBUb2RheSBoZSBzZXJ2ZXMgdGhlIGhlcmQgYSB0b3RhbCBvZiBNICgxICZsdDs9IE0gJmx0Oz0gTikgZGlmZmVyZW50IHR5cGVzIG9mIGZvb2QgKGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5NKS48XC9wPlxyXG5cclxuPHA+VGhlIGNvd3MgYXJlIHBpY2t5LiBDb3cgaSBoYXMgYSBzaW5nbGUgZm9vZCBwcmVmZXJlbmNlIFBfaSAoMSAmbHQ7PSBQX2kgJmx0Oz0gTSkgYW5kIHdpbGwgZWF0IG9ubHkgdGhhdCBmYXZvcml0ZSBmb29kLjxcL3A+XHJcblxyXG48cD5FYWNoIGRheSBhdCBmZWVkaW5nIHRpbWUgRkogY29udmVydHMgdGhlIGJhcm4gaW50byBhIHRhc3RlZnVsbHkgbGl0IGNhZmV0ZXJpYS4gVGhlIGNvd3MgbGluZSB1cCBvdXRzaWRlIHRvIGVudGVyIHRoZSBjYWZldGVyaWEgaW4gb3JkZXIgb2YgdGhlaXIgcHJldmlvdXNseS1tZW50aW9uZWQgY29udmVuaWVudCBpbmRleCBudW1iZXIuPFwvcD5cclxuXHJcbjxwPlVuZm9ydHVuYXRlbHksIHdpdGggc28gbWFueSB0eXBlcyBvZiBmb29kLCBjbGVhbmluZyB1cCBhZnRlcndhcmRzIGlzIHZlcnkgdGltZS1jb25zdW1pbmcuIElmIEZhcm1lciBKb2huIGlzIHNlcnZpbmcgSyBkaWZmZXJlbnQgdHlwZXMgb2YgZm9vZCwgaXQgdGFrZXMgaGltIEsqSyB1bml0cyBvZiB0aW1lIHRvIGNsZWFuIHRoZSBiYXJuLjxcL3A+XHJcblxyXG48cD5UbyBzYXZlIHRpbWUsIEZKIHNlcnZlcyB0aGUgY293cyBpbiBjb250aWd1b3VzIGdyb3VwcyBmcm9tIHRoZSBsaW5lLiBBZnRlciBlYWNoIGdyb3VwLCBoZSBjbGVhbnMgdXAgdGhlIGJhcm4gYW5kIHNldHMgb3V0IHRoZSBmb29kIGZvciB0aGUgbmV4dCBncm91cCAob2YgY291cnNlLCBoZSBvbmx5IHNldHMgb3V0IGZvb2QgdGhhdCBjb3dzIGluIHRoZSBhbnkgZ2l2ZW4gZ3JvdXAgd2lsbCBlYXQpLiBEZXRlcm1pbmUgdGhlIG1pbmltdW0gYW1vdW50IG9mIHRvdGFsIHRpbWUgRkogbXVzdCBzcGVuZCBjbGVhbmluZyB0aGUgYmFybi4gRWFjaCBncm91cCBjb25zaXN0cyBvZiB0aGUgbmV4dCBjb250aWd1b3VzIGdyb3VwIG9mIGNvd3MgZnJvbSB0aGUgbGluZTsgZWFjaCBjb3cgYmVsb25ncyB0byBleGFjdGx5IG9uZSBncm91cDsgYW5kIHRoZSBiYXJuIG11c3QgYmUgY2xlYW5lZCB1cCBhZnRlciBldmVyeSBncm91cCwgaW5jbHVkaW5nIHRoZSBsYXN0IG9uZS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBNPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlcjogUF9pPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXI6IHRoZSBtaW5pbXVtIGFtb3VudCBvZiB0aW1lIEZKIG11c3Qgc3BlbmQgY2xlYW5pbmcgdGhlICZuYnNwO2Jhcm4uPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBmaXJzdCBmb3VyIGdyb3VwcyBjb250YWluIG9uZSBjb3cgZWFjaC4gVGhlIGZpZnRoIGdyb3VwIGNvbnRhaW5zIHR3byBjb3dzIHdobyBwcmVmZXIgZm9vZCAjMiAocmVxdWlyaW5nIG9uZSB1bml0IG9mIHRpbWUpLiBUaGUgc2l4dGggZ3JvdXAgY29udGFpbnMgY293cyBwcmVmZXJyaW5nIGZvb2RzIDMsIDQsIDMsIDQsIDMgKGFuZCByZXF1aXJlcyBmb3VyIHVuaXRzIG9mIHRpbWUgdG8gY2xlYW4pLiBUaGUgbGFzdCB0d28gZ3JvdXBzIGNvbnRhaW4gb25lIGNvdyBlYWNoLiBUaGUgdG90YWwgdGltZSBpcyAxMS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO March 2009 Contest > Gold 2번