Submission #358482

#	Time	Username	Problem	Language	Result	Execution time	Memory
358482		thuanqvbn03	Split the sequence (APIO14_sequence)	C++17	50 / 100	96 ms	131076 KiB

sequence

//Flower_On_Stone
#include <bits/stdc++.h>

using namespace std;

const int MaxN = 100005;

class ConvexHull
{
private:
    const int oo = 1e9;
    struct Segment
    {
        int x, a, id;
        long long b;
        Segment(int _x, int _a = 0, long long _b = 0, int _id = 0) : x(_x), a(_a), b(_b), id(_id) {}
        long long y()
        {
            return 1LL * a * x + b;
        }
        long long getVal(int val)
        {
            return 1LL * a * val + b;
        }
    };
    vector<Segment> segments;
    long long ceil(long long a, long long b)
    {
        assert(b != 0);
        if (b < 0)
        {
            return ceil(-a, -b);
        }
        if (a % b == 0)
        {
            return a / b;
        }
        if (a > 0)
        {
            return a / b + 1;
        }
        return -((-a) / b);
    }

public:
    ConvexHull() {}
    void reset()
    {
        segments.clear();
    }
    void addLine(int a, long long b, int id)
    {
        if (segments.size() && segments.back().a == a && segments.back().b >= b)
        {
            return;
        }
        while (!segments.empty() && 1LL * a * segments.back().x + b >= segments.back().y())
        {
            segments.pop_back();
        }
        if (segments.empty())
        {
            segments.push_back(Segment(0, a, b, id));
            return;
        }
        int inter = ceil(segments.back().b - b, a - segments.back().a);
        if (inter >= 0)
        {
            segments.push_back(Segment(inter, a, b, id));
        }
    }
    pair<long long, int> get(int x)
    {
        int Left = 0, Right = segments.size() - 1;
        while (Left <= Right)
        {
            int Mid = (Left + Right) / 2;
            segments[Mid].x > x ? Right = Mid - 1 : Left = Mid + 1;
        }
        return make_pair(segments[Right].getVal(x), segments[Right].id);
    }
};

int num, numStep;
int a[MaxN];
int prefixSum[MaxN];
long long dp[205][MaxN];
int mark[205][MaxN];
ConvexHull convexHull;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> num >> numStep;
    numStep++;
    for (int i = 1; i <= num; i++)
    {
        cin >> a[i];
        prefixSum[i] = prefixSum[i - 1] + a[i];
    }
    for (int i = 0; i <= numStep; i++)
    {
        fill(dp[i], dp[i] + num + 1, -(long long)1e18);
    }
    dp[0][0] = 0;
    for (int i = 1; i <= numStep; i++)
    {
        convexHull.reset();
        for (int j = 1; j <= num; j++)
        {
            convexHull.addLine(prefixSum[j - 1], dp[i - 1][j - 1] - 1LL * prefixSum[j - 1] * prefixSum[j - 1], j - 1);
            tie(dp[i][j], mark[i][j]) = convexHull.get(prefixSum[j]);
        }
    }
    cout << dp[numStep][num] << '\n';
    vector<int> Res;
    for (int i = numStep - 1; i >= 1; i--)
    {
        Res.push_back(num = mark[i + 1][num]);
    }
    reverse(Res.begin(), Res.end());
    for (auto val : Res)
    {
        cout << val << ' ';
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In constructor 'ConvexHull::Segment::Segment(int, int, long long int, int)':
sequence.cpp:15:19: warning: 'ConvexHull::Segment::b' will be initialized after [-Wreorder]
   15 |         long long b;
      |                   ^
sequence.cpp:14:19: warning:   'int ConvexHull::Segment::id' [-Wreorder]
   14 |         int x, a, id;
      |                   ^~
sequence.cpp:16:9: warning:   when initialized here [-Wreorder]
   16 |         Segment(int _x, int _a = 0, long long _b = 0, int _id = 0) : x(_x), a(_a), b(_b), id(_id) {}
      |         ^~~~~~~

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