제출 #1326688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326688		hoangtien69	수열 (APIO14_sequence)	C++20	71 / 100	215 ms	196608 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 5;
const int INF = LLONG_MAX;

int n, k;
int a[MAXN];
int pre[MAXN], suf[MAXN];
int dp[205][MAXN];
int par[205][MAXN];
vector<int> trace;

struct Line
{
    int a, b;
    int id;
    mutable int p;
    bool operator<(const Line& o) const
    {
        if (o.a == LLONG_MAX && o.b == LLONG_MAX)
            return p < o.p;
        return a < o.a;
    }
};

struct LineContainer
{
    multiset<Line> s;

    int divi(int a, int b)
    {
        if (b == 0) return (a > 0 ? INF : -INF);
        int q = a / b;
        if ((a ^ b) < 0 && a % b) --q;
        return q;
    }
    bool isect(multiset<Line>::iterator x, multiset<Line>::iterator y)
    {
        if (y == s.end())
        {
            x->p = INF;
            return false;
        }
        if (x->a == y->a)
            x->p = (x->b > y->b) ? INF : -INF;
        else
            x->p = divi(y->b - x->b, x->a - y->a);
        return x->p >= y->p;
    }
    void add(int a_, int b_, int id_)
    {
        auto it = s.insert({a_, b_, id_, 0});
        auto y = next(it);

        while (isect(it, y)) y = s.erase(y);
        if (it != s.begin())
        {
            auto x = it;
            --x;
            if (isect(x, it))
                isect(x, s.erase(it));
        }
        while (true)
        {
            auto y = it;
            if (y == s.begin()) break;
            --y;
            if (y->p < it->p) break;
            isect(y, s.erase(it));
            it = y;
        }
    }
    pair<int,int> query(int x)
    {
        Line q{LLONG_MAX, LLONG_MAX, 0, x};
        auto it = s.lower_bound(q);
        if (it == s.end()) --it;
        return {it->a * x + it->b, it->id};
    }
    bool empty()
    {
        return s.empty();
    }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    pre[0] = 0;
    for (int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + a[i];

    suf[n+1] = 0;
    for (int i = n; i >= 1; --i)
        suf[i] = suf[i + 1] + a[i];
    for (int t = 0; t <= k; ++t)
        for (int i = 0; i <= n; ++i)
        {
            dp[t][i] = LLONG_MIN;
            par[t][i] = 0;
        }

    for (int i = 1; i <= n - 1; ++i)
        dp[1][i] = pre[i] * suf[i + 1];

    if (k == 1)
    {
        int ans = LLONG_MIN;
        int pos = 0;
        for (int i = 1; i <= n - 1; ++i)
        {
            if (dp[1][i] > ans)
            {
                ans = dp[1][i];
                pos = i;
            }
        }
        cout << ans << "\n" << pos << "\n";
        return 0;
    }

    for (int t = 2; t <= k; ++t)
    {
        LineContainer cht;

        for (int i = 1; i <= n - 1; ++i)
        {
            if (i - 1 >= t - 1 && dp[t - 1][i - 1] != LLONG_MIN)
            {
                cht.add(-pre[i - 1], dp[t - 1][i - 1], i - 1);
            }

            if (i >= t && !cht.empty())
            {
                auto res = cht.query(suf[i + 1]);
                int val = res.first;
                int id = res.second;
                dp[t][i] = val + suf[i + 1] * pre[i];
                par[t][i] = id;
            }
        }
    }

    int ans = LLONG_MIN;
    int pos = 0;
    for (int i = k; i <= n - 1; ++i)
    {
        if (dp[k][i] > ans)
        {
            ans = dp[k][i];
            pos = i;
        }
    }

    cout << ans << "\n";

    int cur = pos;
    for (int t = k; t >= 1; --t)
    {
        trace.push_back(cur);
        if (t > 1) cur = par[t][cur];
    }
    reverse(trace.begin(), trace.end());
    for (auto v : trace)
        cout << v << " ";
    cout << "\n";
    return 0;
}

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