Submission #1090379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090379		raphaelp	Split the sequence (APIO14_sequence)	C++14	100 / 100	1163 ms	87752 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long N, K;
    cin >> N >> K;
    vector<long long> Tab(N), cum(N + 1);
    for (long long i = 0; i < N; i++)
    {
        cin >> Tab[i];
        cum[i + 1] = cum[i] + Tab[i];
    }
    vector<long long> dp(N);
    vector<vector<int>> dp2(K, vector<int>(N));
    deque<vector<long long>> CHT, CHT2;
    CHT.push_back({0, 0, 0});
    for (long long i = 0; i < K; i++)
    {
        CHT2 = {{0, 0, 0}};
        for (long long j = 0; j < N; j++)
        {
            while (CHT.size() > 1)
            {
                long long m = (CHT[1][0] - CHT[0][0]) / (CHT[1][1] - CHT[0][1]);
                if (cum[N] - cum[j + 1] <= m)
                    CHT.pop_front();
                else
                    break;
            }
            dp[j] = cum[j + 1] * (cum[N] - cum[j + 1]) + CHT.front()[0] - CHT.front()[1] * (cum[N] - cum[j + 1]);
            dp2[i][j] = CHT.front()[2];
            while (CHT2.size() > 1)
            {
                if (CHT2[CHT2.size() - 2][1] == CHT2[CHT2.size() - 1][1] || (double)((dp[j] - CHT2[CHT2.size() - 2][0]) / (cum[j + 1] - CHT2[CHT2.size() - 2][1])) > (double)((CHT2.back()[0] - CHT2[CHT2.size() - 2][0]) / (CHT2.back()[1] - CHT2[CHT2.size() - 2][1])))
                    CHT2.pop_back();
                else
                    break;
            }
            if (CHT2.back()[0] < dp[j])
                CHT2.push_back({dp[j], cum[j + 1], j});
        }
        swap(CHT, CHT2);
    }
    long long best = 0, best2 = 0;
    for (long long i = 0; i < N; i++)
    {
        if (best < dp[i])
        {
            best = dp[i];
            best2 = i;
        }
    }
    cout << best << '\n';
    vector<int> occ(N);
    int buff = 0;
    for (int i = K - 1; i >= 0; i--)
    {
        cout << ((occ[best2]) ? (buff + 1) : (best2 + 1)) << ' ';
        occ[(occ[best2]) ? buff : best2] = 1;
        while (occ[buff])
            buff++;
        best2 = dp2[i][best2];
    }
}

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