Chia nhóm

View as PDF

Submit solution

Points: 0.65 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Ðược add lên bởi canhteo
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho ~N~ số nguyên dương ~A_1, A_2, ..., A_N~. 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 đó.

Ví dụ:

  • ~1\ 2\ 3~ ~\rightarrow~ số giá trị khác nhau bằng ~3~, trọng số ~= 9~.
  • ~1\ 2\ 1~ ~\rightarrow~ số giá trị khác nhau bằng ~2~, trọng số ~= 4~.
  • ~1\ 1\ 1~ ~\rightarrow~ số giá trị khác nhau bằng ~1~, trọng số ~= 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 số nguyên.

Output

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

Sample Input

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

Sample Output

11

Note

Giải thích: Chúng ta sẽ chia dãy số 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~ ~\rightarrow~ ~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 \le 40000~.


Comments

Please read the guidelines before commenting.



  • 3
    hphuonghehe   commented on Nov. 29, 2022, 4:06 p.m.

    test có vẻ hơi yếu, như sol của mình nếu các phần tử bằng nhau thì sẽ chạy trong O(n^2)


    • 0
      khai99   commented on Nov. 29, 2022, 9:30 p.m.

      tuyệt!


  • -6
    YinLin   commented on Aug. 31, 2022, 12:33 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -18
    phanvanhuy   commented on June 7, 2021, 4:43 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -2
      RangDong100years   commented on Oct. 6, 2021, 9:20 p.m.

      có lớn nhất thì nó là 35 nha :v


    • 2
      ngfam   commented on June 7, 2021, 5:08 p.m.

      Bạn đọc kỹ lại đề nhé!