oj.uz

Submission #268113

# Submission time Handle Problem Language Result Execution time Memory
268113 2020-08-16T08:53:02 Z andreiomd Split the sequence (APIO14_sequence) C++11
0 / 100
 2000 ms 512 KB 
#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;
}

Compilation message

sequence.cpp: In function 'void Read()':
sequence.cpp:81:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     freopen("sequence.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   82 |     freopen("sequence.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2039 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -