2024 CCPC 济南 + 山东省赛 VP 记录 + 题解 ACDEFHIJKM

The 2024 CCPC Shandong Invitational Contest and Provincial Collegiate Programming Contest

五月份赛时写了五个题，这次（赛后三个月）个人 VP 了剩下的题目，耗时接近六个小时又写了五个题，括号里是 VP 的罚时，从 300 开始计，没有标记罚时的是五月份赛时写的。

一个人打很容易在一条路上走死，遇到 WA 也找不出 bug……六个小时有四个小时在想为什么 WA，有队友讨论检查的话罚时会少很多……

个人评价难度：

• 签到：I
• 比较基础，广义签到：AKJ
• 略有思维难度：CF
• 需要细心思考：DHM
  （以上都应该在赛时写出来）
• 很天才的想法：EL
• 暂时做不了的：BG

A. Printer (278 + 6)

题意 有$n$ 台打印机，第$i$ 台打印机每$t_{i}$ 秒打印一份试题，但每次打印$l_{i}$ 份试题后要休息$w_{i}$ 秒。如果所有打印机同时工作，打印$k$ 份题至少要多久。

数据范围：$n \leqslant 100$，其余数据$\leqslant 1\times10^{9}$。

思路 题目不难，二分答案即可。唯一考点在于二分要提前返回，否则会爆 LL。

时间复杂度$\Theta(n\log v)$，其中$v=2\times 10^{18}$。

void eachT() {
    int n = read(), k = read();

    vector<ll> t(n), l(n), w(n);
    for (int i = 0; i < n; ++i) {
        t[i] = read(), l[i] = read(), w[i] = read();
    }

    auto check = [&](ll mid) {
        ll sum = 0;
        for (int i = 0; i < n; ++i) {
            ll q = mid / (t[i] * l[i] + w[i]), r = mid % (t[i] * l[i] + w[i]);
            sum += q * l[i] + min(r / t[i], l[i]);
            if (sum >= k) return true;
        }
        return false;
        // return sum >= k;  <- sum 爆 LL
    };

    ll lt = 1, rt = 2e18;
    while (lt <= rt) {
        ll mid = (lt + rt) >> 1;
        if (check(mid)) rt = mid - 1;
        else lt = mid + 1;
    }
    printf("%lld\n", lt);
}

C. Colorful Segments 2 (447 + 2)

题意 给定数轴上的$n$ 条线段，每条线段可以涂上$k$ 种颜色的一种，要求颜色相同的线段不能相交。求方案数。

数据范围：$n \leqslant 5\times 10^{5}$，其余数据$\leqslant 1\times10^{9}$。

思路 按左端点排个序，然后依次染色，如果当前线段与已经染色的$t$ 条线段相交，对答案的贡献是$k-t$。将所有贡献乘起来。

如果用线段树，则是区间加、区间最大值，也可以用堆 (multiset) 维护。

时间复杂度$\Theta(n\log v)$，其中$v=1\times 10^{9}$。

TLE：多测，每次都线段树初始化
WA：没排序

constexpr int mod = 998244353;
constexpr int N = 5e5 + 8;

struct SMT {
    struct info {
        int mx;
        int mrk;
        int l, r;
    } t[N << 6];
    void push_up(info& p, info l, info r) {
        p.mx = max(l.mx, r.mx);
    }
    void push_down(info& p, int d, int l) {
        p.mx += d;
        p.mrk += d;
    }

    // ...
} smt;

void eachT() {
    int n = read(), k = read();
 
    vector<pair<int, int>> a(n);
    for (auto& [l, r] : a) {
        l = read(), r = read();
    }
    sort(a.begin(), a.end());
 
    smt.init(1, 1e9);
 
    ll res = 1;
    for (auto& [l, r] : a) {
        auto qq = smt.query(l, r);
        res *= k - qq.mx;
        res %= mod;
        smt.modify(l, r, 1);
    }
    printf("%lld\n", res);
}

D. Hero of the Kingdom (514 + 3)

队友比较擅长这种题，我自己做写得又慢错误率又高……

题意 买入$x$ 件商品需要$ax + b$ 秒和$px$ 金币，卖出$x$ 件商品需要$cx + d$ 秒赚$qx$ 金币。有$t$ 秒以及初始$m$ 金币，问$t$ 秒结束后最多能有多少金币。

思路 首先有两个结论：尽可能多地买，最终全卖（否则可以不买）。于是问题化为花费$(a+c)x+(b+d)$ 秒赚$(q-p)x$ 金币，其中$x \leqslant \lfloor \cfrac{m}{q} \rfloor$。

思考能不能暴力模拟，不能。最坏情况$q-p=1$，且$x$ 始终为$1$，需要模拟大约$t$ 次，时间不允许。

进一步思考如何用计算代替模拟。如果$x$ 始终不变，我们可以把这一部分的模拟合并为一次，具体来说：

一次性最多买$x$ 个，且$px \leqslant m<p(x+1)$，要求$x$ 始终不变，设这样最多买$l$ 轮次后$x$ 才会变化，有$m+(q-p)x\cdot l \geqslant p(x+1)$，化简得$l=\left\lceil \cfrac{p(x+1)-m}{(q-p)x} \right\rceil$。

那买$l$ 轮的时间够吗？不一定，需要满足$l\cdot[(a+c)x+(b+d)] \leqslant t$，因此$l$ 对$\cfrac{t}{(a+c)x+(b+d)}$ 取最小值。

如果取最小值之后$l=0$，那就 break 不买了吗？也不一定，这时$x$ 的另一个要求是$(a+c)x+(b+d) \leqslant t$，因此$x$ 对$\cfrac{t-(b+d)}{a+c}$ 取最小值。

用这些数据模拟即可。

可以证明这样的循环次数不会太多，经测试最极限的情况大约$10^{4}$ 次量级，$T \leqslant 500$，可以通过。

void eachT() {
    ll p = read(), a = read(), b = read();
    ll q = read(), c = read(), d = read();
    ll m = read(), t = read();

    ll res = 0;
    // int cnt = 0;
    while (t >= b + d) {
        // ++cnt;
        ll x = m / p;
        if (x == 0) break;
        ll lun = min(((x + 1) * p - m + ((q - p) * x) - 1) / ((q - p) * x), t / ((a + c) * x + (b + d)));
        if (lun == 0) {
            x = min(x, (t - (b + d)) / (a + c));
            lun = 1;
        }
        if (x == 0) break;

        m += lun * ((q - p) * x);
        t -= lun * ((a + c) * x + (b + d));
    }
    printf("%lld\n", m);
    // cerr << "cnt = " << cnt << endl;
}

E. Sensors (626)

题意$n$ 个红球$m$ 个监视器，每个监视器监视一个区间，如果区间中只有一个红球则会响铃。依次把某个红球变蓝，每次操作前后输出响铃的监视器下标的平方和。

强制在线。数据范围：$n,m \leqslant 5\times10^{5}$。

思路 这种题一定是类似线段树优化建图或者线段树分治那种的区间连边，那就是把具有同一个性质的监视器合并在一起，但具体维护什么、怎么合并需要思考。

一个想法是按左右端点排序，一个红球能影响的监视器下标是一个范围，这个段数不会太多。但是我们没办法把这些信息合并……

另一个想法是将监视器对应的线段分成若干块，左右端点相同的块的信息共用，这样块数不会很大，一个红球能影响的块数也不会很多，可以通过控制块数达到$\sqrt{n}$ 的复杂度。

实现的时候写线段树就好了，线段树的结构将一个区间划分为$\log n$ 级别个子块，将区间的下标告诉线段树的每个节点，更新时如果经过这个节点就检查对应的监视器。进一步优化，经过某个节点，只有这个节点对应区间的和为$0$ 或$1$ 时才检查对应的监视器，这样严格保证每个节点只会检查两次，每个监视器的每个子块也只会检查两次，保证复杂度在$\log n$ 级别。

时间复杂度$\Theta(m\log n)$，空间$\Theta(n\log n)$。

#define ls p<<1
#define rs p<<1|1
#define mid ((cl+cr)>>1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

void eachT() {
    ll n = read(), m = read();

    vector<vector<int>> vec(m), ids(n << 2);   // vec 监视器对应的树上节点 ids 树上节点对应的监视器 
    vector<int> t(n << 2);

    ll ans = 0;
    vector<int> good(m);
    auto check = [&](int id) {
        int sum = 0;
        for (auto& p : vec[id]) sum += t[p];
        if (good[id]) ans -= (id + 1ll) * (id + 1ll);
        if (sum == 1) ans += (id + 1ll) * (id + 1ll), good[id] = 1;
    };

    auto build = [&](auto&& self, int p, int cl, int cr) -> void {
        if (cl == cr) return t[p] = 1, void();
        self(self, lson), self(self, rson);
        t[p] = t[ls] + t[rs];
    };
    build(build, 1, 0, n - 1);

    for (int id = 0; id < m; ++id) {
        int l = read(), r = read();

        auto dfs = [&](auto&& self, int l, int r, int p, int cl, int cr) -> void {
            if (l <= cl && cr <= r) return ids[p].push_back(id), vec[id].push_back(p);
            if (l <= mid) self(self, l, r, lson);
            if (mid < r)  self(self, l, r, rson);
        };
        dfs(dfs, l, r, 1, 0, n - 1);

        check(id);
    }

    printf("%lld ", ans);
    for (int i = 0; i < n; ++i) {
        int x = (read() + ans) % n;

        auto dfs = [&](auto&& self, int p, int cl, int cr) -> void {
            if (cl == cr) {
                t[p] = 0;
            }
            else {
                if (x <= mid) self(self, lson);
                else self(self, rson);
                t[p] = t[ls] + t[rs];
            }

            if (t[p] == 0 || t[p] == 1) {
                for (auto& id : ids[p]) check(id);
            }
        };
        dfs(dfs, 1, 0, n - 1);

        printf("%lld ", ans);
    }
    printf("\n");
}

F. Divide the Sequence (80 + 3)

题意 将序列分成$k$ 段，设第$i$ 段$[l_{i},r_{i}]$ 的和是$s_{i}=\operatorname{pre}_{r_{i}}-\operatorname{pre}_{l_{i}+1}$，最大化$\sum \limits_{i=1}^{k} is_{i}$，对所有$k$ 求答案。

数据范围：$n \leqslant 5\times10^{5}$。

思路 对于这种$\sum \limits_{i=1}^{k} i\times\square$ 的式子，很常见的做法是作指标变换把$i$ 去掉，所求即是$\sum \limits_{i=1}^{k} \sum \limits_{j=i}^{k}s_{i}=\sum \limits_{i=1}^{k}\operatorname{suf}_{l_{i}}$。这样答案就很显然了，贪心地取后缀和最大的加起来。

如果没有注意到这样的变换，把样例的分段方式算清楚也很容易就能猜到这个结论。

注意是对$n-1$ 个后缀排序，不能包含有$n$ 个元素的那个后缀，因为这个后缀代表着第一个区间，其系数为$0$，不可能产生贡献。

时间复杂度$\Theta(n\log n)$，空间复杂度$\Theta(n)$。

WA：是对$n-1$ 个后缀排序，不能包含有$n$ 个元素的那个后缀，因为$k=1$ 时答案是唯一的。

void eachT() {
    int n = read();

    vector<ll> suf(n);
    for (int i = 0; i < n; ++i) {
        suf[i] = read();
    }
    for (int i = n - 2; i >= 0; --i) {
        suf[i] += suf[i + 1];
    }
    sort(suf.begin() + 1, suf.end());

    ll res = suf[0];
    printf("%lld ", res);
    for (int i = n - 1; i >= 1; --i) {
        res += suf[i];
        printf("%lld ", res);
    }
    printf("\n");
}

H. Stop the Castle (357 + 3)

题意 棋盘上的$n$ 个车会相互攻击，此外有$m$ 个障碍物。问至少再加几个障碍物可以让所有车都不能互相攻击。

数据范围：$n,m \leqslant 200$。

思路 无解情况是有两个车相邻。

尽可能多地将障碍放在十字中心（上下左右都有车）。每对车中间可能有很多十字中心，选择一个即可，但贪心是不可取的。

这种每个东西都要选一个，选的总数尽可能少，与图论中的最小点覆盖很相似，思考如何建模。

事实上，把左右两个相互攻击的车看做二分图左边的点，上下两个看做二分图右边的点，十字中心为边，这就是找二分图的最小点覆盖，即最大匹配。

尽可能多地匹配后，还剩一些未匹配的点，随意把障碍放在两个车中间即可。

WA：未匹配的点需要在尽可能多地匹配后统计，而不是在匹配之前统计。

时间复杂度$\Theta(n^{3})$，空间复杂度$\Theta(n^{2})$。

void eachT() {
    unordered_map<int, vector<pair<int, int>>> X, Y;
    int n = read();
    for (int i = 0; i < n; ++i) {
        int x = read(), y = read();
        X[x].emplace_back(y, 1);
        Y[y].emplace_back(x, 1);
    }
    int m = read();
    for (int i = 0; i < m; ++i) {
        int x = read(), y = read();
        X[x].emplace_back(y, 0);
        Y[y].emplace_back(x, 0);
    }

    vector<array<int, 3>> boy, girl;
    bool ugly = 0;
    for (auto& [x, vec] : X) {
        sort(vec.begin(), vec.end());
        for (int j = 1; j < vec.size(); ++j) {
            auto& [y1, op1] = vec[j - 1];
            auto& [y2, op2] = vec[j];
            if (op1 && op2) {
                if (y1 + 1 == y2) ugly = 1;
                boy.push_back({ x, y1, y2 });
            }
        }
    }
    for (auto& [y, vec] : Y) {
        sort(vec.begin(), vec.end());
        for (int j = 1; j < vec.size(); ++j) {
            auto& [x1, op1] = vec[j - 1];
            auto& [x2, op2] = vec[j];
            if (op1 && op2) {
                if (x1 + 1 == x2) ugly = 1;
                girl.push_back({ y, x1, x2 });
            }
        }
    }

    n = boy.size(), m = girl.size();
    vector<vector<int>> E(n);
    for (int u = 0; u < n; ++u) {
        auto& [x, y1, y2] = boy[u];
        for (int v = 0; v < m; ++v) {
            auto& [y, x1, x2] = girl[v];
            if (x1 < x && x < x2 && y1 < y && y < y2) {
                E[u].push_back(v);
            }
        }
    }

    if (ugly) {
        printf("-1\n");
        return;
    }

    vector<int> npy(m, -1);
    for (int u = 0; u < n; ++u) {
        vector<int> vis(m, 0);
        auto dfs = [&](auto&& self, int u) -> bool {
            for (auto& v : E[u]) {
                if (vis[v]) continue;
                vis[v] = 1;
                if (npy[v] == -1 || self(self, npy[v])) {
                    npy[v] = u;
                    return true;
                }
            }
            return false;
        };
        dfs(dfs, u);
    }

    vector<pair<int, int>> res;
    vector<int> happy(n, false);
    for (int v = 0; v < m; ++v) {
        if (npy[v] != -1) {
            happy[npy[v]] = true;
            res.emplace_back(boy[npy[v]][0], girl[v][0]);
        }
        else {
            auto& [y, x1, x2] = girl[v];
            res.emplace_back(x1 + x2 >> 1, y);
        }
    }
    for (int u = 0; u < n; ++u) {
        if (!happy[u]) {
            auto& [x, y1, y2] = boy[u];
            res.emplace_back(x, y1 + y2 >> 1);
        }
    }

    printf("%d\n", res.size());
    for (auto& [x, y] : res) {
        printf("%d %d\n", x, y);
    }
}

I. Left Shifting (5)

题意 给定字符串，问至少左移几次之后，字符串的首尾字符相同。

void eachT() {
    string s;
    cin >> s;

    const int n = s.size();

    for (int i = 0; i < n; ++i) {
        if (s[i] == s[(i + n - 1) % n]) {
            cout << i << endl;
            return;
        }
    }
    cout << -1 << endl;
}

J. Colorful Spanning Tree (129)

题意 一张完全图，每个点有颜色，共有$n$ 种颜色，其中第$i$ 种颜色的点有$a_{i}$ 个。两点之间的边权由两点的颜色决定，求该完全图的最小生成树。

数据范围：$n \leqslant 1\times10^{3},\ a_{i} \leqslant 1\times10^{6}$。

思路 先把同一种颜色的点缩在一起，看成一个大点，对于所有的大点构成的图的最小生成树（就是最朴素的 Kurskal 或 Prim）。再考虑每个大点内部怎么连边，只需要对其中$a_{i}-1$ 个点每个点选择另一个点连边，那贪心地在$n$ 种边权中选最小的即可。能够证明这样一定构成一棵树。

时空复杂度$\Theta(n^{2})$。

void eachT() {
    int n = read();

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        a[i] = read();
    }

    ll ans = 0;
    vector E(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        int mn = 0x3f3f3f3f;
        for (int j = 0; j < n; ++j) {
            E[i][j] = read();
            mn = min(mn, E[i][j]);
        }
        ans += mn * (a[i] - 1ll);
    }

    // Prim
    vector<int> dis(n, 0x3f3f3f3f);
    vector<int> vis(n, 0);
    dis[0] = 0;
    for (int t = 0; t < n; ++t) {
        int u = -1;
        for (int j = 0; j < n; ++j) {
            if (!vis[j] && (u == -1 || dis[j] < dis[u])) u = j;
        }
        vis[u] = 1;
        ans += dis[u];
        for (int v = 0; v < n; ++v) {
            dis[v] = min(dis[v], E[u][v]);
        }
    }

    printf("%lld\n", ans);
}

K. Matrix (43)

题意 构造一个$n\times n$ 的矩阵，元素范围从$1$ 到$2n$。要求$1$ 到$2n$ 每种元素至少出现一次，且恰有一个子矩阵的四角元素互不相同。

思路 一定有解，构造方式不唯一，如

$$\begin{matrix} 1 & 2 & 6 & 8 \\ 4 & 3 & 6 & 8 \\ 6 & 6 & 5 & 8 \\ 8 & 8 & 8 & 7 \end{matrix}$$

时空复杂度$\Theta(n^{2})$。

void eachT() {
    int n = read();

    vector a(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            a[i][j] = a[j][i] = i + 1 << 1;
        }
        a[i][i] = i << 1 | 1;
    }
    a[0][1] = 2;

    printf("Yes\n");
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
}

*L. Intersection of Paths (UPSOLVE)

int rt, L, R;
struct SMT {
    int pcnt;
    struct info {
        ll a, b, c, ab, bc, abc;
        ll mrk;
        int l, r;
    } t[N << 3];

    void init(int l, int r) {
        pcnt = 0, rt = 0;
        L = l, R = r;
    }

    void init(int p) {
        t[p] = { 0, 0, 0, 0, 0, 0, 0, 0 };
    }

#define ls t[p].l
#define rs t[p].r
#define mid ((cl+cr)>>1)
#define len (cr-cl+1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

    void push_up(info& p, info l, info r) {
        p.a = max(l.a, r.a);
        p.b = max(l.b, r.b);
        p.c = max(l.c, r.c);
        p.ab = max({ l.ab, r.ab, l.a + r.b });
        p.bc = max({ l.bc, r.bc, l.b + r.c });
        p.abc = max({ l.abc, r.abc, l.ab + r.c, l.a + r.bc });
    }

    void push_down(info& p, ll d, int l) {
        p.a += d;
        p.b -= 2 * d;
        p.c += d;
        p.ab -= d;
        p.bc -= d;
        p.mrk += d;
    }

    void push_up(int p) { push_up(t[p], t[ls], t[rs]); }
    void push_down(int p, int l) {
        push_down(t[ls], t[p].mrk, l - (l >> 1));
        push_down(t[rs], t[p].mrk, l >> 1);
        t[p].mrk = 0;
    }

    void build(auto& arr, int& p = rt, int cl = L, int cr = R) {
        p = ++pcnt, init(p);
        if (cl == cr) return push_down(t[p], arr[cl], 1);
        build(arr, lson), build(arr, rson);
        return push_up(p);
    }

    void modify(int l, int r, ll d, int& p = rt, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) return push_down(t[p], d, len);
        push_down(p, len);
        if (l <= mid) modify(l, r, d, lson);
        if (mid < r)  modify(l, r, d, rson);
        return push_up(p);
    }

    info query(int l, int r, int& p = rt, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) return t[p];
        push_down(p, len);
        if (r <= mid) return query(l, r, lson);
        if (mid < l)  return query(l, r, rson);
        info res;
        push_up(res, query(l, r, lson), query(l, r, rson));
        return res;
    }
} smt;

vector<pair<int, int>> E[N];  // [v, id]
int son[N];  // 边对应的另一端点 
ll w[N];     // 边权 
ll dep[N];
int siz[N];
int tfn[N], tfnR[N], tseq[N << 1], tunix;  // 全 DFS 序 
void dfs(int u, int p) {
    tseq[++tunix] = u;
    tfn[u] = tunix;
    siz[u] = 1;
    for (auto& [v, id] : E[u]) {
        if (v == p) continue;
        son[id] = v;
        dep[v] = dep[u] + w[id];
        dfs(v, u);
        siz[u] += siz[v];
        tseq[++tunix] = u;
    }
    tfnR[u] = tunix;
}

void init() {
    dfs(1, 0);
    smt.init(1, tunix);
    vector<ll> arr(tunix + 1);
    for (int i = 1; i <= tunix; i++) {
        arr[i] = dep[tseq[i]];
    }
    smt.build(arr);
}

void change(int id, ll e) {
    int v = son[id];
    smt.modify(tfn[v], tfnR[v], -w[id]);
    w[id] = e;
    smt.modify(tfn[v], tfnR[v], w[id]);
}

ll get() {
    return smt.query(1, tunix).abc;
}

void eachT() {
    int n = read(), q = read();

    for (int id = 1; id < n; id++) {
        int u = read(), v = read();
        w[id] = read();
        E[u].emplace_back(v, id);
        E[v].emplace_back(u, id);
    }

    init();

    vector<vector<int>> vec(n);
    for (int id = 1; id < n; id++) {
        int v = son[id];
        vec[min(siz[v], n - siz[v])].push_back(id);
    }

    vector<vector<tuple<int, int, int>>> que(n);
    for (int qid = 0; qid < q; qid++) {
        int id = read(), e = read(), k = read();
        que[k].emplace_back(id, e, qid);
    }

    vector<ll> ans(q);
    for (int k = 1; k < n; k++) {
        for (auto& [id, e, qid] : que[k]) {
            int old = w[id];
            if (old) change(id, e);
            ans[qid] = get();
            change(id, old);
        }
        for (auto& id : vec[k]) {
            change(id, 0);
        }
    }

    for (int i = 0; i < q; i++) {
        printf("%lld\n", ans[i]);
    }
}

M. Palindromic Polygon (432 + 10)

先是 WA，以为我的优化在最坏情况下没有优化，所以换了一种写法，然后 TLE 了。以为复杂度没算错，所以在各种常数优化又多了很多罚时。其实第一次提交是最接近正解的……

题意 给一个凸多边形，每个顶点有个权值。选择若干个顶点，使得从某个点开始，逆时针转一圈构成的权值序列是回文序列（注意与回文串的区别）。求这些顶点的凸包的最大面积。

数据范围：$n \leqslant 500$。

思路 类似区间 DP，从中心向两边扩展，或者从两边往中间缩，本题更适合第二种。

注意设状态$f_{l,r}$ 表示以$l,r$ 为端点的回文序列，而不是子串$l\sim r$ 中的回文序列，后者无法转移。

有一个贪心优化是，往中间缩时找到的$l_{1},r_{1}$（$a_{l_{1}}=a_{r_{1}}$），要么$l_{1}$ 和$l$ 之间没有与$a_{l_{1}}$ 相等的数，要么$r_{1}$ 和$r$ 之间没有与$a_{l_{1}}$ 相等的数，这样的转移复杂度是$2n$，不需要$n^{2}$ 转移，时间复杂度少了一个量级。

代码写的是记忆化搜索，不大会 DP 的写法。

时间复杂度$\Theta(n^{3})$，空间复杂度$\Theta(n^{2})$。

struct Vector {
    ll x, y;
    ll operator*(Vector o) { return x * o.y - y * o.x; }
};

struct Point {
    ll x, y;
    Vector operator-(Point o) { return Vector(x - o.x, y - o.y); }
};

ll Area(Point a, Point b, Point c) {
    return abs((b - a) * (c - a));
}

void eachT() {
    int n;
    cin >> n;

    vector<int> a(n << 1);
    vector<int> alls;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        alls.push_back(a[i]);
    }

    sort(alls.begin(), alls.end());
    unique(alls.begin(), alls.end());
    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(alls.begin(), alls.end(), a[i]) - alls.begin();
        a[i + n] = a[i];
    }

    vector lst(n << 1, vector<int>(n, -1)), nxt(n << 1, vector<int>(n, n << 1));
    for (int i = 0; i < n << 1; ++i) {
        if (i) lst[i] = lst[i - 1];
        lst[i][a[i]] = i;
    }
    for (int i = (n << 1) - 1; i >= 0; --i) {
        if (i != (n << 1) - 1) nxt[i] = nxt[i + 1];
        nxt[i][a[i]] = i;
    }

    vector<Point> pos(n << 1);
    for (int i = 0; i < n; i++) {
        cin >> pos[i].x >> pos[i].y;
        pos[i + n] = pos[i];
    }

    vector dp(n << 1, vector<ll>(n << 1, -1));
    auto dfs = [&](auto&& self, int L, int R) -> ll {
        if (dp[L][R] != -1) return dp[L][R];
        if (a[L] != a[R]) return dp[L][R] = 0;
        if (L + 1 >= R) return dp[L][R] = 0;

        ll res = 0;
        for (int l = L + 1; l < R; ++l) {
            int r = lst[R - 1][a[l]];
            res = max(res, self(self, l, r) + Area(pos[L], pos[l], pos[R]) + Area(pos[l], pos[r], pos[R]));
        }
        for (int r = R - 1; r > L; --r) {
            int l = nxt[L + 1][a[r]];
            res = max(res, self(self, l, r) + Area(pos[L], pos[l], pos[R]) + Area(pos[l], pos[r], pos[R]));
        }
        return dp[L][R] = res;
    };

    ll res = 0;
    for (int l = 0; l < n << 1; ++l) {
        for (int r = l; r < min(l + n, n << 1); ++r) {
            if (a[l] == a[r])
                res = max(res, dfs(dfs, l, r));
        }
    }
    cout << res << '\n';
}