Submission #341909

#	Time	Username	Problem	Language	Result	Execution time	Memory
341909		blue	Split the sequence (APIO14_sequence)	C++11	0 / 100	27 ms	6716 KiB

sequence

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

//int dp[n+1][k+1]; // maximum score obtainable from 1..i by making j cuts.
//if(j+1 > i) dp[i][j] = irrelevant

//dp[i][j] = max(x = 1..i-1, dp[x][j-1] + (a[i] - a[x])*a[x])
//dp[i][j] = max(x = 1..i-1, dp[x][j-1] + a[i]*a[x] - a[x]*a[x])
//                         = a[x]*a[i] + dp2[x] - a[x]^2

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

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

    vector<long long> dp2(n+1), dp(n+1);

    for(int i = 0; i <= n; i++) dp2[i] = 0; //0 cuts;

    deque<long long> A, B, I; // a*x + b

    int prev[n+1][k+1];

    for(int cuts = 1; cuts <= k; cuts++)
    {
        A.clear();
        B.clear();
        I.clear();

        I.push_back(cuts);
        A.push_back(a[cuts]);
        B.push_back(dp2[cuts] - a[cuts]*a[cuts]);
        for(int i = cuts+1; i <= n; i++)
        {
            while(A.size() >= 2 && A[0]*a[i] + B[0] < A[1]*a[i] + B[1])
            {
                I.pop_front();
                A.pop_front();
                B.pop_front();
            }
            dp[i] = A[0]*a[i] + B[0];
            prev[i][cuts] = I[0];
            // cout << prev[i][cuts] << ' ';
            // cout << i << " -> " << A[0] << ' ' << B[0] << '\n';

            A.push_back(a[i]);
            B.push_back(dp2[i] - a[i]*a[i]);
            I.push_back(i);
        }
        // cout << '\n';
        swap(dp, dp2);

        // for(int i = 1; i <= n; i++) cout << dp2[i] << ' ';
        // cout << '\n';
    }
    cout << dp2[n] << '\n';
    int curr = n;
    for(int i = k; i >= 1; i--)
    {
        curr = prev[curr][i];
        cout << curr << ' ';
    }
    cout << '\n';
}

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