Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CTNCLN - Chia nhóm

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/ctncln


Cho N số nguyên dương A1,A2...An. Mỗi số có giá trị không vượt quá N .

Yêu cầu :

Hãy chia N số này thành một số nhóm sao cho:

-Mỗi nhóm là một dãy các số liên tiếp.

-Trọng số của mỗi nhóm được tính theo công thức : Bình phương của số giá trị khác nhau trong nhóm đó.

        VD + 1 2 3 -> số giá trị khác nhau bằng 3 .

             + 1 2 1  -> số giá trị khác nhau bằng 2.

             + 1 1 1  -> số giá trị khác nhau bằng 1.

+Trọng số của dãy số bằng Tổng trọng số của tất cả các nhóm . Hãy tìm cách chia sao cho Tổng trọng số đạt giátrị nhỏ nhất.

Input

Dòng 1 : Gồm 2 số N và M - Số lượng số và số giá trị khác nhau trong dãy.

Dòng 2..N+1 : Mỗi dòng chứa một ố nguyên .

Output

Trọng số nhỏ nhất của dãy số.

Example

Input:

13 4
1
2
1
3
2
2
3
4
3
4
3
1
4
Output:
11

Giải thích : Chúng ta sẽ chia dãy ố thành 8 nhóm
+ 4 nhóm đầu tiên mỗi nhóm chứa một số duy nhất.
+ nhóm thứ 5 chứa hai số nguyên đều có giá trị là 2.
+ nhóm thứ 6 gồm các số từ 7->12 : (3, 4, 3, 4, 3)
+ 2 nhóm cuối cùng mỗi nhóm gồm 1 số duy nhất.

Kết quả là 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 2^2 + 1^2 + 1^2= 11.

Giới hạn: N<=40000.

Được gửi lên bởi:Phan Công Minh
Ngày:2009-09-17
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Được add lên bởi canhteo

hide comments
2017-09-27 09:46:36
Code tham khảo: http://123link.top/CTNCLN
2017-09-13 07:38:30
Code AC: http://shink.in/PMchb
2017-02-27 14:21:44
theo đề từ USACO thì giá trị lớn nhất của dãy ko vượt quá M
@phanduy16
2014-07-23 14:33:53 Lollipop
cho M là gì vậy ??
2012-12-08 07:37:54 Shinken Yellow
M<= ? vậy
2011-04-06 11:43:22 T-7
Hình như mỗi số có giá trị không quá M thì đúng hơn :D
2011-03-19 06:48:30 Tran Dang Tuan Anh
Bài này nguồn từ USACO thì phải :d
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.