Description

传送门

Solution

每次选择花费最大的地方切，然后按照题意(O(n))模拟即可。

证明如下：

(1.)若两次切割都是横向或竖向，且花费小的比花费大的先切割。
设花费小的切割的时候需要切割(a)次，花费大的切割的时候需要切割(b)次，因为中间可能切割了任意次另外一个方向，所以(a 。
那么将它们交换，则花费大的对答案的贡献一定小于等于原先的贡献，所以同一方向将花费大的放在花费小的前面一定最优。
(2.)若两次切割不是同一方向，且话费晓得比花费大的先切割。
设切割前若切花费小的方向花费小的方向需要切(a)刀，切花费大的方向需要切(b)刀。
那么先切花费小的，花费大的就需要切(b + 1)刀，反之亦然。
因为花费大的(\times (b + 1) +)花费小的(\times a >=)花费大的(\times b +)花费小的(\times (a + 1))，所以先切花费大的一定最优。
所以最后复杂度就是排序的复杂度。

[Q.E.D. ]

Code

#include 
#include 
#include 
#include 
using namespace std;
#define ll long long
const int N = 20000;
int n, m, num, sum[2];
struct Node
{
    int cost, type;
} cut[N + 50];
void Read(int &x)
{
    x = 0; int p = 0; char st = getchar();
    while (st  '9') p = (st == '-'), st = getchar();
    while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
    x = p ? -x : x;
    return;
}
bool Cmp(Node a, Node b)
{
    return a.cost > b.cost;
}
int main()
{
    ll ans = 0;
    Read(n); Read(m);
    for (int i = 1, x; i <= n - 1; i++) Read(x), cut[++num] = (Node){x, 1};
    for (int i = 1, x; i <= m - 1; i++) Read(x), cut[++num] = (Node){x, 0};
    sort(cut + 1, cut + num + 1, Cmp);
    for (int i = 1; i <= num; i++)
    {
        ans = ans + 1LL * (sum[cut[i].type ^ 1] + 1) * cut[i].cost;
        sum[cut[i].type]++;
    }
    printf("%lld", ans);
    return 0;
}