Submission #84149

#	Time	Username	Problem	Language	Result	Execution time	Memory
84149		Alexa2001	Split the sequence (APIO14_sequence)	C++17	100 / 100	1543 ms	83920 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Kmax = 205, Nmax = 1e5 + 5;

ll dp[2][Nmax];
int opt[Kmax][Nmax], S[Nmax], A[Nmax];
int n, k;

ll cost(int x, int y) { return (ll) (S[y] - S[x-1]) * (S[y] - S[x-1]); }

void divide(int K, int st, int dr, int L, int R)
{
    int mid = (st + dr) / 2, i;
    dp[K&1][mid] = 1e18;

    for(i=L; i<=R && i<mid; ++i)
    {
        ll C = dp[(K&1)^1][i] + cost(i+1, mid);
        if(C < dp[K&1][mid]) dp[K&1][mid] = C, opt[K][mid] = i;
    }

    if(st <= mid-1) divide(K, st, mid-1, L, opt[K][mid]);
    if(mid+1 <= dr) divide(K, mid+1, dr, opt[K][mid], R);
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i;
    cin >> n >> k;
    for(i=1; i<=n; ++i)
    {
        cin >> A[i];
        S[i] = S[i-1] + A[i];
    }

    for(i=1; i<=n; ++i) dp[0][i] = 1e18;

    for(i=1; i<=k+1; ++i)
    {
        divide(i, i, n, 0, n-1);
        int j;
        for(j=0; j<i; ++j) dp[i&1][j] = 1e18;
    }

    cout << (cost(1, n) - dp[(k+1)&1][n]) / 2 << '\n';

    vector<int> positions;
    for(i=k+1; i>=2; --i)
    {
        positions.push_back(opt[i][n]);
        n = opt[i][n];
    }

    for(i=k-1; i>=0; --i) cout << positions[i] << ' ';
    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