제출 #715196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715196		four_specks	수열 (APIO14_sequence)	C++17	89 / 100	718 ms	98880 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

namespace
{
    template <typename T>
    T fl_div(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }

} // namespace

struct Line
{
    long m, c;
    int id;

    long operator()(long x) const { return m * x + c; }
};

long isect(const Line &l1, const Line &l2) { return fl_div(l1.c - l2.c, l2.m - l1.m); }

void solve()
{
    int n, k;
    cin >> n >> k;

    vector<long> a(n);
    for (long &x : a)
        cin >> x;

    vector<long> pref(n + 1);
    for (int i = 0; i < n; i++)
        pref[i + 1] = pref[i] + a[i];

    vector prv(n + 1, vector(k + 1, -1));
    vector<deque<Line>> dp(k + 1);

    dp[0].push_back({0, 0, 0});
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i + 1] == 0)
            continue;

        for (int j = 0; j < k; j++)
        {
            while ((int)dp[j].size() >= 2 && dp[j][1](pref[i + 1]) >= dp[j][0](pref[i + 1]))
                dp[j].pop_front();
            prv[i + 1][j + 1] = dp[j][0].id;
            Line line = {pref[i + 1], dp[j][0](pref[i + 1]) - pref[i + 1] * pref[i + 1], i + 1};
            while ((int)dp[j + 1].size() >= 2 && isect(line, dp[j + 1].back()) <= isect(dp[j + 1].back(), dp[j + 1].end()[-2]))
                dp[j + 1].pop_back();
            dp[j + 1].push_back(line);
        }
    }

    while ((int)dp[k].size() >= 2 && dp[k][1](pref[n]) >= dp[k][0](pref[n]))
        dp[k].pop_front();

    long res = dp[k][0](pref[n]);

    vector<int> pos;
    for (int i = dp[k][0].id, j = k; i > 0; i = prv[i][j--])
        pos.push_back(i);
    reverse(pos.begin(), pos.end());

    cout << res << '\n';
    for (int i : pos)
        cout << i << ' ';
    cout << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

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