oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

cleanup Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

cleanup.html

In the good old days, Kang the Penguin served a boring cuisine comprising but a single type of penguin food to his N (1 ≤ N ≤ 40,000) junior penguins. Times change. Today he serves his juniors a total of M (1 ≤ M ≤ N) different types of food (conveniently numbered 1..M).

The junior penguins are picky. Penguin i has a single food preference Pi (1 ≤ Pi ≤ M) and will eat only that favorite food.

Each day at feeding time Kang converts the penguin hideout into a tastefully lit cafeteria. The penguins line up outside to enter the cafeteria in order of their previously-mentioned convenient index number.

Unfortunately, with so many types of food, cleaning up afterwards is very time-consuming. If Kang the penguin is serving K different types of food, it takes him K*K units of time to clean the hideout.

To save time, Kang serves the penguins in contiguous groups from the line. After each group, he cleans up the hideout and sets out the food for the next group (of course, he only sets out food that penguins in the any given group will eat). Determine the minimum amount of total time Kang must spend cleaning the hideout. Each group consists of the next contiguous group of penguins from the line; each penguin belongs to exactly one group; and the hideout must be cleaned up after every group, including the last one.

Input

  • Line 1: Two space-separated integers: N and M
  • Lines 2..N+1: Line i+1 contains a single integer: Pi

Output

Line 1: A single integer: the minimum amount of time Kang must spend cleaning up.

Sample Input 1

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

Explanation for Sample Input 1

There are four types of food and thirteen penguins in line. The first penguin prefers type 1, the second type 2, the third type 1, etc.

Sample Output 1

11

Explanation for Sample Output 1

The first four groups contain one penguin each. The fifth group contains two penguins who prefer food #2 (requiring one unit of time). The sixth group contains penguins preferring foods 3, 4, 3, 4, 3 (and requires four units of time to clean). The last two groups contain one penguin each. The total time is 11.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110091s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o cleanup -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.