Aitaus

#include <bits/stdc++.h>

#define ll long long 
#define pii pair<ll, ll>
#define pllk pair<long long, long long>
#define M 1000000007
#define INF 0x5ADFACE5
#define LINF 0x51DEEFFEC7C0DECALL
#define N (1<<17)

using namespace std;

ll dp[1111][1111];
ll o[1111][1111];
ll s[1111];

int main () {
	ll n;
	cin>>n;
	vector<ll> v(n + 1);
	for (ll i = 1; i <= n; i++) {
		cin>>v[i];
	}
	sort(v.begin() + 1, v.end());
	for (ll i = 1; i <= n; i++) s[i] = v[i] + s[i - 1];
	for (ll l = 1; l <= n; l++) {
		for (ll x = 1; x <= n; x++) {
			ll y = x + l - 1;
			if (y > n) continue;
			if (l == 1) continue;
			if (l == 2) {
				o[x][y] = x;
				dp[x][y] = s[y] - s[x - 1];
			} else {
				dp[x][y] = LINF;
				for (ll k = max(o[x][y - 1], (x + y) / 2); k <= o[x + 1][y]; k++) {
					ll p = dp[x][y];
					dp[x][y] = min(dp[x][y], dp[x][k] + dp[k + 1][y]);
					if (p != dp[x][y]) o[x][y] = k;
				}
				dp[x][y] += s[y] - s[x - 1];
			}
		}
	}
	cout<<dp[1][n]<<endl;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: RUNTIME ERROR

Test 12

Group: 3

Verdict: RUNTIME ERROR

Test 13

Group: 3

Verdict: RUNTIME ERROR

Test 14

Group: 3

Verdict: RUNTIME ERROR

Test 15

Group: 3

Verdict: RUNTIME ERROR