Submission #1327207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1327207		Double_Slash	Split the sequence (APIO14_sequence)	C++20	100 / 100	600 ms	83444 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 1e18;

struct Line {
    int a;
    ll b;

    ll operator()(int x) const { return (ll) a * x + b; }

    Line operator-(const Line &o) const { return {a - o.a, b - o.b}; }

    ll operator*(const Line &o) const { return a * o.b - o.a * b; }
};

struct CHT : deque<Line> {
    void add(const Line &o) {        
        while (size() >= 2 and (back() - end()[-2]) * (o - end()[-2]) >= 0) pop_back();
        push_back(o);
    }

    ll query(int x) {
        while (size() >= 2 and front()(x) > begin()[1](x)) pop_front();
        return front()(x);
    }
};
int n, k, a[100000], dp[100000][201];
ll ps[100001];

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ps[i] = (i ? ps[i - 1] : 0) + a[i];
    }
    vector<ll> cur(n, INF);
    for (int j = 0; j <= k; ++j) {
        vector<ll> nxt(n);
        CHT cht;
        cht.add({0, 0});
        for (int i = 0; i < n; ++i) {
            dp[i][j] = (nxt[i] = ps[i] * ps[i] + cht.query(ps[i])) % INT32_MAX;
            if (a[i]) cht.add({-2 * ps[i], ps[i] * ps[i] + cur[i]});
        }
        cur = move(nxt);
    }
    ll ans = cur.back();
    cout << (ps[n - 1] * ps[n - 1] - ans) / 2 << endl;
    ll ps = 0;
    for (int i = n; k;) {
        ps += a[--i];
        if ((dp[i - 1][k - 1] + ps * ps) % INT32_MAX == ans % INT32_MAX) {
            ans -= ps * ps;
            k--;
            ps = 0;
            cout << i << " ";
        }
    }
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:46:35: warning: narrowing conversion of '(-2 * ps[i])' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   46 |             if (a[i]) cht.add({-2 * ps[i], ps[i] * ps[i] + cur[i]});
      |                                ~~~^~~~~~~

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