Submission #838678

#	Time	Username	Problem	Language	Result	Execution time	Memory
838678		popovicirobert	Split the sequence (APIO14_sequence)	C++14	100 / 100	1631 ms	83400 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

constexpr long long INF = 1e18;

constexpr int MAXN = (int) 1e5;
constexpr int MAXK = 200;

long long dp[2][MAXN + 1];
int from[MAXK + 2][MAXN + 1];

struct Line {
    long long a, b;
    int id;

    Line(long long a, long long b, int id) : a(a), b(b), id(id) {}
};

int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, k;
    cin >> n >> k;
    k++;

    vector<long long> sum(n + 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum[i] = sum[i - 1] + x;
    }

    auto Eval = [](const Line l, long long x) {
        return l.a * x + l.b;
    };

    auto Inter = [](const Line l1, const Line l2) -> double {
        if (l1.a == l2.a)
            return 1.0 * INF;
        return 1.0 * (l2.b - l1.b) / (l1.a - l2.a);
    };

    auto Get = [&](long long x, const vector<Line>& lines) -> pair<long long, int> {
        int result = 0;
        for (int step = 1 << 16; step; step >>= 1) {
            if (result + step + 1 < (int)lines.size() && Eval(lines[result + step], x) >= Eval(lines[result + step + 1], x)) {
                result += step;
            }
        }

        pair<long long, int> answer = {Eval(lines[result], x), lines[result].id};
        if (result + 1 < (int)lines.size()) {
            long long curr = Eval(lines[result + 1], x);
            if (answer.first > curr) {
                answer = {curr, lines[result + 1].id};
            }
        }
        return answer;
    };

    for (int i = 0; i <= n; i++) {
        dp[1][i] = 1LL * sum[i] * sum[i];
    }

    vector<Line> lines;

    for (int j = 2; j <= k; j++) {
        lines.clear();

        for (int i = j; i <= n; i++) {
            long long a = -2 * sum[i - 1];
            long long b = dp[1 - j & 1][i - 1] + sum[i - 1] * sum[i - 1];
            auto l = Line(a, b, i - 1);

            while ((int)lines.size() > 1 && Inter(lines[lines.size() - 2], lines.back()) - Inter(lines[lines.size() - 2], l) >= 0) {
                lines.pop_back();
            }
            lines.push_back(l);

            auto curr = Get(sum[i], lines);
            dp[j & 1][i] = 1LL * sum[i] * sum[i] + curr.first;
            from[j][i] = curr.second;
        }
    }

    cout << (1LL * sum[n] * sum[n] - dp[k & 1][n]) / 2 << "\n";

    do {
        n = from[k][n];
        cout << n << " ";
        k--;
    } while (k > 1);

    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:78:32: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   78 |             long long b = dp[1 - j & 1][i - 1] + sum[i - 1] * sum[i - 1];
      |                              ~~^~~

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