题意

现在，有一个$n\ast n$的网格图，左下角坐标是$(1,1)$，右上角坐标是$(n,n)$。有一个小$SB$正在坐标为$(n,1)$的位置，每一时刻，如果他现在在$(x,y)$，他可以选择走到$(x-1,y+1)$ 或者$(x,(y+1)div2)$，如果选择后者，他要支付$B_x$的代价。
其中$B$为数组$A$的后缀和。

思路

首先可以想到动态规划，乱搞一下$O(N^2)$，只有50分。
然后看一下题解发现是合并果子，直接怒切。
有待研究~

代码

#pragma GCC optimize(2)
#include<queue>
#include<cstdio>std::priority_queue<int> q;
int t, n;
long long ans;long long input() {char c = getchar();int f = 1;long long result = 0;while (c < '0' || c > '9') {if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') {result = result * 10 + (c - 48);c = getchar();}return result * f;
}void print(long long x) {if (x > 9) print(x / 10);putchar(x % 10 + 48);
}int main() {t = input();for (; t; t--) {n = input();ans = 0;int x, y;for (int i = 1; i <= n; i++) {x = input();q.push(-x);}while ((int)q.size() >= 2) {x = -q.top();q.pop();y = -q.top();q.pop();ans += x + y;q.push(-x - y);}q.pop();print(ans);putchar(10);}
}