Submission #838694

#	Time	Username	Problem	Language	Result	Execution time	Memory
838694		popovicirobert	Split the sequence (APIO14_sequence)	C++14	100 / 100	544 ms	81032 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 Cmp = [](const Line l1, const Line l2, const Line l3) {
        return (l2.b - l1.b) * (l2.a - l3.a) >= (l3.b - l2.b) * (l1.a - l2.a);
    };

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

    for (int j = 2; j <= k; j++) {
        deque<Line> lines;
        
        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 && Cmp(lines[lines.size() - 2], lines.back(), l)) {
                lines.pop_back();
            }
            lines.push_back(l);
            while ((int)lines.size() > 1 && Eval(lines[0], sum[i]) >= Eval(lines[1], sum[i])) {
                lines.pop_front();
            }

            auto curr = make_pair(Eval(lines[0], sum[i]), lines[0].id);
            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:56:32: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   56 |             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