1-watermelon.cpp by anonymous

#include <iostream>
using namespace std;
const int N = 5005, INF = 1e9;
int n, a[N];
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  long long ans = 0;
  while (n > 1) {
    int pos1 = -1, val1 = INF;
    int pos2 = -1, val2 = INF;
    for (int i = 1; i <= n; ++i) {
      if (a[i] < val1) {
        val2 = val1, pos2 = pos1;
        val1 = a[i], pos1 = i;
      } else if (a[i] < val2) {
        val2 = a[i], pos2 = i;
      }
    }
    ans += val1 + val2;
    a[pos1] = val1 + val2;
    a[pos2] = a[n];
    --n;
  }
  cout << ans << endl;
  return 0;
}