Submission #861565

#	Time	Username	Problem	Language	Result	Execution time	Memory
861565		sleepntsheep	Split the sequence (APIO14_sequence)	C++17	0 / 100	21 ms	8028 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)*1.0/(l.m-m)*1.0;
    }
};

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

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;
            cht.add(line{p[i], dp[!(j&1)][i] - p[i]*p[n], i});
        }
        cht.clear();
    }
    return 0;
}

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