Particle accelerator

#include <bits/stdc++.h>

using namespace std;

const long long INF = 9223372036854775807;

int main()
{
    int n;
    cin >> n;
    vector<int> weights(n);
    for (int i = 0; i < n; i++)
    {
        cin >> weights[i];
    }

    // idea: dp[l][r] is min energy for combining all particles from l to r
    vector<vector<long long>> dp(n);
    vector<long long> weight_sums(n + 1);

    for (int i = 0; i < n; i++)
    {
        dp[i] = vector<long long>(n, INF);
        dp[i][i] = 0;
        // prefix sum: weight_sums[k+1] = weight of all particles until k (included)
        weight_sums[i + 1] = weight_sums[i] + weights[i];
    }

    for (int length = 2; length <= n; length++)
    {
        for (int l = 0; l <= n - length; l++)
        {
            int r = l + length - 1;
            for (int k = l; k < r; k++)
            {
                long long mass_1 = weight_sums[k + 1] - weight_sums[l];
                long long mass_2 = weight_sums[r + 1] - weight_sums[k + 1];
                long long merge_cost = mass_1 * mass_2 - pow(min(mass_1, mass_2), 2);
                assert(dp[l][k] != INF && dp[k + 1][r] != INF);
                long long total = dp[l][k] + dp[k + 1][r] + merge_cost;
                dp[l][r] = min(dp[l][r], total);
            }
        }
    }

    cout << dp[0][n - 1] << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED

Test 65

Verdict: ACCEPTED

Test 66

Verdict: ACCEPTED

Test 67

Verdict: ACCEPTED

Test 68

Verdict: ACCEPTED

Test 69

Verdict: ACCEPTED

Test 70

Verdict: ACCEPTED

Test 71

Verdict: ACCEPTED

Test 72

Verdict: ACCEPTED

Test 73

Verdict: ACCEPTED

Test 74

Verdict: ACCEPTED

Test 75

Verdict: ACCEPTED

Test 76

Verdict: ACCEPTED

Test 77

Verdict: ACCEPTED

Test 78

Verdict: ACCEPTED

Test 79

Verdict: WRONG ANSWER

Test 80

Verdict: ACCEPTED

Test 81

Verdict: ACCEPTED

Test 82

Verdict: ACCEPTED

Test 83

Verdict: ACCEPTED

Test 84

Verdict: ACCEPTED

Test 85

Verdict: ACCEPTED

Test 86

Verdict: ACCEPTED

Test 87

Verdict: ACCEPTED

Test 88

Verdict: ACCEPTED

Test 89

Verdict: ACCEPTED

Test 90

Verdict: ACCEPTED

Test 91

Verdict: ACCEPTED