题解 | 最优划分

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, b;
    if (!(cin >> n >> b)) return 0;
    vector<long long> a(n+1);
    for (int i = 1; i <= n; ++i) {
        long long x; cin >> x;
        a[i] = llabs(x); // 取绝对值，确保gcd合法
    }

    if (b > n) {
        // 无法把正长度连续段切成比元素更多的份
        // 依据你们评测要求：可以输出 -1 或把 b 截断到 n。
        // 这里选择直接判无解：
        cout << -1 << "\n";
        return 0;
    }

    const long long NEG = LLONG_MIN / 4;
    vector<long long> prev(n+1, NEG), cur(n+1, NEG);
    prev[0] = 0; // 0 个元素切成 0 段的得分为 0

    for (int k = 1; k <= b; ++k) {
        // 用一个压缩的 gcd 向量表示所有以 i 结尾的后缀 gcd 状态
        vector<pair<long long,long long>> vec; // (gcd, best_base)
        fill(cur.begin(), cur.end(), NEG);

        for (int i = 1; i <= n; ++i) {
            vector<pair<long long,long long>> nvec;
            nvec.reserve(vec.size() + 1);

            // 新开一段，从 i 开始：段内 gcd = a[i]，上一层贡献 = prev[i-1]
            if (prev[i-1] != NEG) {
                nvec.emplace_back(a[i], prev[i-1]);
            }

            // 继承旧段：把所有以 i-1 结尾的后缀段延长到 i
            for (auto &p : vec) {
                long long g = std::gcd(p.first, a[i]);
                long long base = p.second;
                if (!nvec.empty() && nvec.back().first == g) {
                    nvec.back().second = max(nvec.back().second, base);
                } else {
                    nvec.emplace_back(g, base);
                }
            }

            // 由于不同来源可能得到相同的 gcd，再做一次线性合并去重（按相同 gcd 合并最大 base）
            // （上面已做“相邻”合并，但这里再稳妥合并所有）
            vector<pair<long long,long long>> merged;
            merged.reserve(nvec.size());
            sort(nvec.begin(), nvec.end(), [](auto &L, auto &R){
                return L.first < R.first; // 按 gcd 升序，便于进一步合并
            });
            for (auto &p : nvec) {
                if (!merged.empty() && merged.back().first == p.first) {
                    merged.back().second = max(merged.back().second, p.second);
                } else {
                    merged.push_back(p);
                }
            }

            // 计算 cur[i] = max(base + gcd)
            long long best = NEG;
            for (auto &p : merged) {
                if (p.second != NEG) best = max(best, p.second + p.first);
            }
            cur[i] = best;

            // 下一轮继承使用的 vec 就是当前 i 的 gcd 压缩列表
            // 为了下一个 i 快速更新，按“不增加随机开销”的方式存为不排序、相邻去重的形态更好。
            // 不过我们此处选择保持“按原顺序+相邻去重”的形式：把 merged 再按 gcd 降序还原并相邻合并。
            // 事实上为简洁起见，直接把 merged（升序且唯一）赋给 vec 也可，下一步取 gcd 仍然正确。
            vec = std::move(merged);
        }
        prev.swap(cur);
    }

    long long ans = prev[n];
    if (ans == NEG) ans = -1; // 若无解
    cout << ans << "\n";
    return 0;
}