제출 #1090368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1090368		raphaelp	수열 (APIO14_sequence)	C++14	60 / 100	106 ms	131072 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<vector<long long>> dp(K, vector<long long>(N)), dp2(K, vector<long long>(N));
    deque<vector<long long>> CHT, CHT2;
    CHT.push_back({0, 0, 0});
    for (long long i = 0; i < K; i++)
    {
        CHT2 = {{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[i][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[i][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[i][j])
                CHT2.push_back({dp[i][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[K - 1][i])
        {
            best = dp[K - 1][i];
            best2 = i;
        }
    }
    cout << best << '\n';
    for (int i = K - 1; i >= 0; i--)
    {
        cout << best2 + 1 << ' ';
        best2 = dp2[i][best2];
    }
}

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