Submission #562754

#	Time	Username	Problem	Language	Result	Execution time	Memory
562754		Cyanmond	Split the sequence (APIO14_sequence)	C++17	100 / 100	842 ms	86460 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

constexpr i64 inf = 1ll << 40;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)

template <typename T> bool chmax(T &a, const T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

class CHT {
    deque<pair<i64, i64>> deq;

    int pm(i64 v) { return v == 0 ? 0 : (v > 0 ? 1 : -1); }

    bool check(pair<i64, i64> a, pair<i64, i64> b, pair<i64, i64> c) {
        if (a.second == b.second or b.second == c.second)
            return pm(b.first - a.first) * pm(c.second - b.second) <=
                   pm(c.first - b.first) * pm(b.second - a.second);
        else
            return double(b.first - a.first) * pm(c.second - b.second) /
                       double(abs(b.second - a.second)) <=
                   double(c.first - b.first) * pm(b.second - a.second) /
                       double(abs(c.second - b.second));
    }

  public:
    void add(pair<i64, i64> line) {
        if (deq.empty()) {
            deq.push_back(line);
            return;
        }
        assert(line.first >= deq.back().first);
        if (deq.back().first == line.first) {
            if (deq.back().second > line.second)
                deq.pop_back();
            else
                return;
        }
        while (deq.size() >= 2 and check(deq[deq.size() - 2], deq.back(), line)) deq.pop_back();
        deq.push_back(line);
    }

    pair<i64, i64> query(i64 x) {
        while (deq.size() >= 2 and
               (deq[0].first * x + deq[0].second >= deq[1].first * x + deq[1].second))
            deq.pop_front();
        return {deq[0].first, deq[0].first * x + deq[0].second};
    }
};

int main() {
    int N, K;
    cin >> N >> K;
    ++K;
    vector<i64> A(N);
    for (auto &e : A) cin >> e;
    vector<i64> R(N + 1);
    REP(i, N) R[i + 1] = R[i] + A[i];
    auto calc_sum = [&R](int l, int r) { return R[r] - R[l]; };

    vector<i64> dp(N + 1, -inf);
    dp[0] = 0;
    vector<vector<int>> db(N + 1, vector<int>(K + 1));
    REP(k, K) {
        CHT cht;
        cht.add({calc_sum(0, k), -dp[k]});
        auto ndp = dp;
        REP3(i, k + 1, N + 1) {
            const auto [x, v] = cht.query(calc_sum(i, N));
            ndp[i] = -v + calc_sum(0, i) * calc_sum(i, N);
            db[i][k + 1] = x;
            if (i != N) cht.add({calc_sum(0, i), -dp[i]});
        }
        dp = move(ndp);
    }

    cout << dp[N] << endl;
    int now = N;
    vector<int> data;
    REP(i, K - 1) {
        int nxt = now;
        --nxt;
        while (calc_sum(0, nxt) != db[now][K - i]) --nxt;
        data.push_back(nxt);
        now = nxt;
    }
    reverse(data.begin(), data.end());
    REP(i, K - 1) cout << data[i] << (i == K - 1 ? '\n' : ' ');
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29