Submission #861577

#	Time	Username	Problem	Language	Result	Execution time	Memory
861577		sleepntsheep	Split the sequence (APIO14_sequence)	C++17	100 / 100	684 ms	83016 KiB

sequence

#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;
using ld = long double;

#define N 100002
#define ALL(x) x.begin(), x.end()
int n, k, a[N];
ll p[N], dp[2][N];
int bt[202][N];

/*
 * dp[j][i] = 0..i with j-th split happening at between a[i] and a[i+1]
 *
 * dp[j][i] = max(dp[j-1][k] + (p[i] - p[k]) * (p[n] - p[i]))
 *          = p[i]p[n] - p[i]p[i] + max(p[i]p[k] + dp[j-1][k] - p[k]p[n])
 **/

struct line
{
    ll m, c; int id;
    ll operator[](ll x) { return m*x+c; }
    ll intersectx(const line &l) { return (c-l.c)/(l.m-m); }
};

struct ConvexHullTrick : deque<line>
{
    void add(line l)
    {
        while (size() > 1 && 
                ((back().m == l.m && l.c >= back().c) ||
                 (back().intersectx((*this)[size()-2]) >= back().intersectx(l)))) pop_back();
        push_back(l);
    }
    line query(ll x)
    {
        while (size() > 1 && front()[x] <= (*this)[1][x]) pop_front();
        return front();
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i], p[i] = p[i-1] + a[i];

    ConvexHullTrick cht;
    for (int j = 1; j <= k + 1; ++j)
    {
        cht.add(line{0, 0, -1});
        for (int i = 1; i <= n; ++i)
        {
            line lne = cht.query(p[i]);
            dp[j&1][i] = p[i]*p[n] - p[i]*p[i] + lne[p[i]];
            bt[j][i] = lne.id;
            if (j != 1) cht.add(line{p[i], dp[!(j&1)][i] - p[i]*p[n], i});
        }
        cht.clear();
    }

    deque<int> path;
    for (int c = bt[k+1][n], j = k; j >= 0 && c != -1;) path.push_front(c), c = bt[j--][c];

    cout << dp[(k+1)&1][n] << '\n';
    for (auto x : path) cout << x << ' ';

    return 0;
}

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