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++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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.



  • 0
    meanthai  commented on Feb. 22, 2023, 5:23 a.m.

    chia mỗi số 1 nhóm hã ông =)))))


  • 2
    hphuonghehe  commented on Nov. 29, 2022, 9:06 a.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)


    • -1
      khai99  commented on Nov. 29, 2022, 2:30 p.m.

      tuyệt!


  • -9
    YinLin  commented on Aug. 31, 2022, 5:33 a.m.

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


  • -19
    phanvanhuy  commented on June 7, 2021, 9:43 a.m.

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


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

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


    • 1
      ngfam  commented on June 7, 2021, 10:08 a.m.

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