Submission #97447

#	Time	Username	Problem	Language	Result	Execution time	Memory
97447		Kastanda	Split the sequence (APIO14_sequence)	C++11	100 / 100	1119 ms	81916 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005, K = 205;
int n, k, lvl, w, P[K][N];
ll A[N], dp[2][N];
inline ll Get(int l, int r)
{
    return ((A[r] - A[l]) * (A[r] - A[l]));
}
void Solve(int l, int r, int le, int ri)
{
    if (r < l)
        return ;
    int md = (l + r) >> 1, opt = -1;
    ll Mn = 2e18;
    for (int i = le; i <= min(ri, md); i++)
        if (Mn >= Get(i - 1, md) + dp[!w][i - 1])
            Mn = Get(i - 1, md) + dp[!w][i - 1], opt = i;
    dp[w][md] = Mn;
    P[lvl][md] = opt - 1;
    Solve(l, md - 1, le, opt);
    Solve(md + 1, r, opt, ri);
}
int main()
{
    ll sum = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &A[i]), A[i] += A[i - 1];
    memset(dp, 63, sizeof(dp)); dp[0][0] = 0;
    for (lvl = 1; lvl <= k + 1; lvl ++)
        w = lvl & 1, Solve(1, n, 1, n), dp[0][0] = 2e18;
    printf("%lld\n", (A[n] * A[n] - dp[w][n]) >> 1);
    vector < int > vec;
    for (int i = k + 1, nw = P[i][n]; i > 1; i--, nw = P[i][nw])
        vec.push_back(nw);
    reverse(vec.begin(), vec.end());
    for (int i : vec) printf("%d ", i);
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:27:8: warning: unused variable 'sum' [-Wunused-variable]
     ll sum = 0;
        ^~~
sequence.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:30:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &A[i]), A[i] += A[i - 1];
         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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