Submission #170298

#	Time	Username	Problem	Language	Result	Execution time	Memory
170298		Kastanda	Split the sequence (APIO14_sequence)	C++11	100 / 100	1045 ms	81432 KiB

sequence

// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005, K = 209;
int n, k, lvl, 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, int j)
{
    if (r < l) return ;
    int md = l + r >> 1, opt = -1;
    dp[j][md] = (ll)2e18;
    for (int i = le; i <= min(ri, md); i ++)
        if (dp[j][md] >= dp[!j][i - 1] + Get(i - 1, md))
            dp[j][md] = dp[!j][i - 1] + Get(i - 1, md), opt = i;
    P[lvl][md] = opt - 1;
    Solve(l, md - 1, le, opt, j);
    Solve(md + 1, r, opt, ri, j);
}
int main()
{
    scanf("%d%d", &n, &k); 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; lvl ++)
        Solve(1, n, 1, n, lvl & 1), dp[0][0] = (ll)2e18;
    printf("%lld\n", (A[n] * A[n] - dp[k & 1][n]) / 2);
    vector < int > V;
    for (; k > 1; k --)
        V.push_back(P[k][n]), n = P[k][n];
    reverse(V.begin(), V.end());
    for (int i : V)
        printf("%d ", i);
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void Solve(int, int, int, int, int)':
sequence.cpp:15:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int md = l + r >> 1, opt = -1;
              ~~^~~
sequence.cpp: In function 'int main()':
sequence.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k); k ++;
     ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:28: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