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

formation Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

formation.html

Problem Description

Damian is currently helping out as an orientation group leader. For the next activity, he has to divide the N participants under his care into groups of 3.

As we all know, everyone is crazy. Thus everyone has an associated craziness value Vi. When people are put together in a group, however, things become even worse - suffice to say, it multiplies like crazy! The effective craziness of a group consisting of three people with craziness values of a, b and c is given by f(a, b, c) = a * b * c.

Not wanting to stress himself out more than necessary, Damian would like to form as many groups as possible, while minimising the sum of the effective craziness of the groups. People without a group do not contribute to this sum. Help him find this minimum sum.

Input

The first line contains one integer, N, the number of participants present.

The second line contains N space-separated integers, with the ith integer representing the craziness value of the ith participant.

Output

The output should contain one line containing one integer, the minimum sum of f(a, b, c) that can be achieved while still forming as many teams as possible.

Limits

For all subtasks, 0 ≤ Vi ≤ 106.

Subtask 1 (7%): 1 ≤ N ≤ 3.

Subtask 2 (19%): 1 ≤ N ≤ 11.

Subtask 3 (43%): 1 ≤ N ≤ 15.

Subtask 4 (18%): 1 ≤ N ≤ 17.

Subtask 5 (13%): 1 ≤ N ≤ 20.

Subtask 6 (0%): Sample Testcases.

Sample Testcase 1

Input

7
4 19 3 8 7 5 4

Output

232

Sample Output 1 Explanation

For the participants with craziness levels 3, 4, 4, 5, 7 and 8, the optimal way of grouping is (3, 5, 8) and (4, 4, 7) which gives a total of 3 * 5 * 8 + 4 * 4 * 7 = 232

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
17111s256MBMinimum
219111s256MBMinimum
343111s256MBMinimum
418111s256MBMinimum
513111s256MBMinimum
6011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o formation -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.