Submission #438847

#	Time	Username	Problem	Language	Result	Execution time	Memory
438847		blue	Split the sequence (APIO14_sequence)	C++17	100 / 100	870 ms	82996 KiB

sequence

#include <iostream>
#include <deque>
using namespace std;

/*
dp[c][i] = min{dp[c-1][j] + (a_sum[i] - a_sum[j]) * a_sum[j] | 1 <= j < i}
         = min{a_sum[j] * a_sum[i]   +   dp[c-1][j] - a_sum[j]^2    | 1 <= j < i}
                 A        * X           +        B
*/

struct line
{
    long long a;
    long long b;
    int i;

    long long eval(long long x)
    {
        return a*x + b;
    }
};

long long sq(long long x)
{
    return x*x;
}


bool intersect_comp(line l1, line l2, line r1, line r2)
{
    //intersect(l1, l2) <=> l1.a * x + l1.b == l2.a * x + l2.b
    /*
        xL = (l2.b - l1.b)/(l1.a - l2.a)
        xR = (r2.b - r1.b)/(r1.a - r2.a)

        xL < xR <=> ()
    */

    return (l2.b - l1.b)*(r1.a - r2.a) < (r2.b - r1.b)*(l1.a - l2.a);
}



int main()
{
    int n, k;
    cin >> n >> k;

    long long a[n+1], a_sum[n+1];
    a_sum[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a_sum[i] = a[i] + a_sum[i-1];
    }

    long long* dp[k+1];
    int* prev[k+1];

    dp[0] = new long long[n+1];
    dp[1] = new long long[n+1];

    prev[0] = new int[n+1];
    prev[1] = new int[n+1];

    for(int x = 2; x <= k; x++)
    {
        dp[x] = dp[x-2];
        prev[x] = new int[n+1];
    }

    for(int i = 0; i <= n; i++)
    {
        dp[0][i] = 0;
        prev[0][i] = 0;
    }

    for(int c = 1; c <= k; c++)
    {
        prev[c][1] = 0;
        dp[c][1] = 0;

        deque<line> cht;
        cht.push_back(line{a_sum[1], dp[c-1][1] - sq(a_sum[1]), 1});
        for(int i = 2; i <= n; i++)
        {
            while(cht.size() > 1 && cht[0].eval(a_sum[i]) <= cht[1].eval(a_sum[i]))
                cht.pop_front();

            dp[c][i] = cht[0].eval(a_sum[i]);
            prev[c][i] = cht[0].i;

            line new_line = line{a_sum[i], dp[c-1][i] - sq(a_sum[i]), i};
            while(cht.size() > 1 && !intersect_comp(cht[cht.size()-2], cht[cht.size()-1],  cht.back(), new_line))
                cht.pop_back();

            cht.push_back(new_line);
        }
    }


    cout << dp[k][n] << '\n';
    int x = n, y = k;
    for(y = k; y >= 1; y--)
    {
        cout << prev[y][x] << ' ';
        x = prev[y][x];
    }
    cout << '\n';
}

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