Submission #30158

#	Time	Username	Problem	Language	Result	Execution time	Memory
30158		Andrei1998	Split the sequence (APIO14_sequence)	C++14	50 / 100	2000 ms	42116 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 10000 + 5;
const int KMAX = 200 + 5;
typedef long long int lint;
const lint INF = 2E18;

int N, K;
int sPart[NMAX];
pair <lint, int> dpBrute[KMAX][NMAX];
int father[KMAX][NMAX];

void brute() {
    dpBrute[1][0] = {INF, 0};
    for (int j = 1; j <= N; ++ j)
        dpBrute[1][j] = {1LL * sPart[j] * sPart[j], 0};
    for (int i = 2; i <= K; ++ i) {
        dpBrute[i][0] = {INF, 0};
        for (int j = 1; j <= N; ++ j) {
            dpBrute[i][j] = {1LL * (sPart[j] - sPart[j - 1]) * (sPart[j] - sPart[j - 1]) + dpBrute[i - 1][j - 1].first, j - 1};
            for (int k = 1; k <= j; ++ k)
                dpBrute[i][j] = min(dpBrute[i][j], {1LL * (sPart[j] - sPart[k - 1]) * (sPart[j] - sPart[k - 1]) + dpBrute[i - 1][k - 1].first, k - 1});
        }
    }
}

int main()
{
    cin >> N >> K;
    ++ K;
    for (int i = 1; i <= N; ++ i) {
        int val;
        cin >> val;
        sPart[i] = val + sPart[i - 1];
    }

    brute();
    cout << (1LL * sPart[N] * sPart[N] - dpBrute[K][N].first) / 2 << '\n';

    vector <int> sol;

    int where = N;
    int k = K;
    while (dpBrute[k][where].second) {
        sol.push_back(dpBrute[k][where].second);
        where = dpBrute[k --][where].second;
    }

    reverse(sol.begin(), sol.end());
    for (int i = 0; i < sol.size(); ++ i)
        cout << sol[i] << " \n"[i + 1 == sol.size()];
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < sol.size(); ++ i)
                       ^
sequence.cpp:53:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         cout << sol[i] << " \n"[i + 1 == sol.size()];
                                       ^

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