记录编号	611243	评测结果	AAAAAAAAAA
题目名称	石子合并III	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	8.115 s
提交时间	2026-01-24 17:30:04	内存使用	3.85 MiB

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define int long long
int n;
int ans = 0;
vector<int> a;

void merge(int k){
	int tmp = a[k - 1] + a[k];
	ans += tmp;
	a.erase(a.begin() + k - 1);
	a.erase(a.begin() + k - 1);
	int pos = -1;
	for(int i = k - 2;i >= 0;i --){
		if(a[i] >= tmp){
			pos = i;
			break;
		}
	}
	a.insert(a.begin() + pos + 1, tmp);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i ++){
		int val; cin >> val;
		a.push_back(val);
	}
	while(a.size() > 1){
		int k = a.size() - 1;
		for(int i = 1;i < (int)a.size() - 1;i ++){
			if(a[i - 1] <= a[i + 1]){
				k = i;
				break;
			}
		}
		merge(k);
	}
	cout << ans << '\n';
	return 0;
}