Submission #268116

#	Time	Username	Problem	Language	Result	Execution time	Memory
268116		andreiomd	Split the sequence (APIO14_sequence)	C++11	71 / 100	2056 ms	83448 KiB

sequence

#include <iostream>
#include <cstdio>

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5 + 5, KMAX = 2e2 + 5;
const long long INF = 1LL * 1e18;

int N, K;

int sp[NMAX];
long long p[NMAX];

long long ans, dp[NMAX][2];

int Keep[NMAX][KMAX];
int V[KMAX];

namespace InParser
{
static const int BSIZE = (1 << 16);

static int pos = BSIZE - 1;
static char buff[BSIZE];

static inline char Char ()
{
    ++pos;

    if(pos == BSIZE)
    {
        pos = 0;

        int n = fread(buff, 1, BSIZE, stdin);

        if(n != BSIZE)
            for(int i = n; i < BSIZE; ++i)
                buff[i] = 0;
    }

    return buff[pos];
}

inline int Int ()
{
    int ans = 0;

    for( ; ; )
    {
        char Ch = Char();

        if(Ch >= '0' && Ch <= '9')
        {
            ans = (int)(Ch - '0');

            break;
        }
    }

    for( ; ; )
    {
        char Ch = Char();

        if(Ch >= '0' && Ch <= '9')
            ans = ans * 10 + (int)(Ch - '0');
        else
            break;
    }

    return ans;
}
};

static inline void Read ()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    /// freopen("sequence.in", "r", stdin);
    /// freopen("sequence.out", "w", stdout);

    N = InParser :: Int(), K = InParser :: Int();

    for(int i = 1; i <= N; ++i)
    {
        int A = InParser :: Int();

        sp[i] = sp[i - 1] + A;
        p[i] = p[i - 1] + 1LL * A * A;
    }

    return;
}

static inline int Query_1 (int Left, int Right)
{
    if(Left > Right)
        return 0;

    return sp[Right] - sp[(Left - 1)];
}

static inline void Load ()
{
    for(int i = 1; i <= N; ++i)
        ans += 1LL * (1LL * Query_1(i, i) * Query_1(i + 1, N));

    return;
}

static inline long long Query_2 (int Left, int Right)
{
    if(Left > Right)
        return 0;

    return p[Right] - p[(Left - 1)];
}

static inline long long Cost (int Left, int Right)
{
    if(Left > Right)
        return 0;

    long long a = Query_1(Left, Right);
    long long b = Query_2(Left, Right);

    return ((1LL * (1LL * a * a - 1LL * b)) >> 1LL);
}

static inline void Go (int Left, int Right, int Chosen_Left, int Chosen_Right, int Level)
{
    if(Left > Right)
        return;

    int Mid = ((Left + Right) >> 1);
    int Chosen = Mid;

    for(int k = Chosen_Left; k <= min(Mid, Chosen_Right); ++k)
    {
        long long Now = dp[k - 1][((Level - 1) & 1)] + Cost(k, Mid);

        if(Now < dp[Mid][(Level & 1)])
            dp[Mid][(Level & 1)] = Now, Chosen = k;
    }

    Keep[Mid][Level] = Chosen;

    Go(Left, Mid - 1, Chosen_Left, Chosen, Level);
    Go(Mid + 1, Right, Chosen, Chosen_Right, Level);

    return;
}

static inline void Initialize ()
{
    for(int i = 0; i <= N; ++i)
        for(int j = 0; j < (2 - (K == 1)); ++j)
            dp[i][j] = INF;

    for(int i = 1; i <= N; ++i)
        dp[i][1] = Cost(1, i);

    for(int i = 1; i <= N; ++i)
        Keep[i][1] = i;

    return;
}

static inline void Write ()
{
    int pos = N;

    for(int i = (K + 1); i > 1; --i)
        pos = V[i - 1] = Keep[pos][i] - 1;

    for(int i = 1; i <= K; ++i)
    {
        printf("%d", V[i]);

        if(i != K)
            printf(" ");
    }

    printf("\n");

    return;
}

static inline void Solve ()
{
    Initialize();

    for(int j = 2; j <= (K + 1); ++j)
        Go(j, N, j, N, j);

    ans -= 1LL * dp[N][((K + 1) & 1)];

    printf("%lld\n", ans);

    Write();

    return;
}

int main()
{
    Read();

    Load();

    Solve();

    return 0;
}

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