Submission #569839

#	Time	Username	Problem	Language	Result	Execution time	Memory
569839		Stickfish	Split the sequence (APIO14_sequence)	C++17	100 / 100	1048 ms	89224 KiB

sequence

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const int MAXN = 1e5 + 123;
const int MAXK = 200;
const ll INF = 1e18 + 177013;
int a[MAXN];
int opt[MAXK][MAXN];
ll dp[MAXN];
ll ndp[MAXN];
ll sm[MAXN];

ll divup(ll a, ll m) {
    return (a + m - 1) / m;
}

struct line {
    ll b;
    ll k;
    int i;

    line(ll b_, ll k_, int i_): b(b_), k(k_), i(i_) {}

    ll operator()(ll x) {
        return k * x + b;
    }

    ll where_better(line l) {
        if (k == l.k) {
            if (b <= l.b)
                return 0;
            else
                return INF;
        }
        return divup(b - l.b, l.k - k);
    }
};

void back_track(int i, int lyr) {
    if (lyr == 0) {
        cout << opt[lyr][i] + 1 << ' ';
        return;
    }
    back_track(opt[lyr][i], lyr - 1);
    cout << opt[lyr][i] + 1 << ' ';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i) {
        sm[i] += a[i];
        if (i)
            sm[i] += sm[i - 1];
        dp[i] = 1ll * sm[i] * sm[i];
    }

    for (int lyr = 0; lyr < k; ++lyr) {
        vector<pair<ll, line>> cht;
        cht.push_back({0, {0, 0, -1}});
        int j = 0;
        for (int i = 0; i < n; ++i) {
            j = min(j, int(cht.size()) - 1);
            //j = 0;
            while (j + 1 < cht.size() && sm[i] >= cht[j + 1].first)
                ++j;
            ndp[i] = cht[j].second(sm[i]) + 1ll * sm[i] * sm[i];
            opt[lyr][i] = cht[j].second.i;
            line l(dp[i] + 1ll * sm[i] * sm[i], -2ll * sm[i], i);
            while (true) {
                if (cht.empty()) {
                    cht.push_back({0, l});
                    break;
                }
                ll x = l.where_better(cht.back().second);
                if (x <= cht.back().first) {
                    cht.pop_back();
                } else {
                    cht.push_back({x, l});
                    break;
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            dp[i] = min(dp[i], ndp[i]);
        }
    }
    cout << (1ll * sm[n - 1] * sm[n - 1] - dp[n - 1]) / 2 << endl;;
    back_track(n - 1, k - 1);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:72:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, line> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             while (j + 1 < cht.size() && sm[i] >= cht[j + 1].first)
      |                    ~~~~~~^~~~~~~~~~~~

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