Submission #30164

#	Time	Username	Problem	Language	Result	Execution time	Memory
30164		Andrei1998	Split the sequence (APIO14_sequence)	C++14	100 / 100	1079 ms	84352 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

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

int N, K;
int sPart[NMAX];
int father[KMAX][NMAX];

/*lint dpBrute[2][NMAX];
void brute() {
    dpBrute[1][0] = INF;
    for (int j = 1; j <= N; ++ j)
        dpBrute[1][j] = 1LL * sPart[j] * sPart[j];
    for (int i = 2; i <= K; ++ i) {
        for (int j = 0; j < i; ++ j)
            dpBrute[i & 1][j] = INF;
        for (int j = i; j <= N; ++ j) {
            pair <lint, int> sol = {1LL * (sPart[j] - sPart[j - 1]) * (sPart[j] - sPart[j - 1]) + dpBrute[(i - 1) & 1][j - 1], j - 1};
            for (int k = i - 1; k <= j; ++ k)
                sol = min(sol, {1LL * (sPart[j] - sPart[k - 1]) * (sPart[j] - sPart[k - 1]) + dpBrute[(i - 1) & 1][k - 1], k - 1});
            dpBrute[i & 1][j] = sol.first;
            father[i][j] = sol.second;
        }
    }
}*/

lint dp[2][NMAX];

bool fail;
inline long double intersect(int i, int k1, int k2) {
    if (sPart[k2 - 1] == sPart[k1 - 1]) {
        fail = true;
        return -1;
    }
    else {
        fail = false;
        return 1.0L * (1LL * sPart[k2 - 1] * sPart[k2 - 1] + dp[(i - 1) & 1][k2 - 1] - 1LL * sPart[k1 - 1] * sPart[k1 - 1] - dp[(i - 1) & 1][k1 - 1]) / (2LL * (sPart[k2 - 1] - sPart[k1 - 1]));
    }
}

void solve() {
    dp[1][0] = INF;
    for (int j = 1; j <= N; ++ j)
        dp[1][j] = 1LL * sPart[j] * sPart[j];
    deque <int> dq;
    for (int i = 2; i <= K; ++ i) {
        for (int j = 0; j < i; ++ j)
            dp[i & 1][j] = INF;
        dq.clear();

        for (int j = i; j <= N; ++ j) {
            //Add j
            while (dq.size() > 1) {
                int k1 = dq.at(dq.size() - 2);
                int k2 = dq.at(dq.size() - 1);
                int k3 = j;

                bool decision = (intersect(i, k1, k2) + 1E-10 >= intersect(i, k1, k3));
                assert(!fail);
                if (decision)
                    dq.pop_back();
                else
                    break;
            }

            if (dq.empty())
                dq.push_back(j);
            else {
                intersect(i, dq.back(), j);
                if (!fail)
                    dq.push_back(j);
            }

            //While first gets beaten by second
            while (dq.size() > 1) {
                int k1 = dq.at(0);
                int k2 = dq.at(1);

                lint val1 = 1LL * (sPart[j] - sPart[k1 - 1]) * (sPart[j] - sPart[k1 - 1]) + dp[(i - 1) & 1][k1 - 1];
                lint val2 = 1LL * (sPart[j] - sPart[k2 - 1]) * (sPart[j] - sPart[k2 - 1]) + dp[(i - 1) & 1][k2 - 1];

                if (val2 <= val1)
                    dq.pop_front();
                else
                    break;
            }

            //First is best
            int k = dq.front();
            dp[i & 1][j] = 1LL * (sPart[j] - sPart[k - 1]) * (sPart[j] - sPart[k - 1]) + dp[(i - 1) & 1][k - 1];
            father[i][j] = k - 1;
        }
    }
}

int main()
{
    //freopen("data.in", "r", stdin);
    ios_base :: sync_with_stdio(false);

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

    //brute();
    solve();

    cout << (1LL * sPart[N] * sPart[N] - dp[K & 1][N]) / 2 << '\n';

    vector <int> sol;

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

    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:129:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < sol.size(); ++ i)
                       ^
sequence.cpp:130: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: 21 / 21
• Subtask 6: 29 / 29