Submission #1279793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279793		_filya_	Split the sequence (APIO14_sequence)	C++20	100 / 100	575 ms	83668 KiB

sequence

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

// struct Line {
//     mutable ll k, m, p, num;
//     bool operator<(const Line& o) const { return k < o.k; }
//     bool operator<(ll x) const { return p < x; }
// };
// struct LineContainer : multiset<Line, less<>> {
//     static const ll inf = LLONG_MAX;
//     ll div(ll a, ll b) {
//         return a / b - ((a ^ b) < 0 && a % b); }
//     bool isect(iterator x, iterator y) {
//         if (y == end()) return x->p = inf, 0;
//         if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
//         else x->p = div(y->m - x->m, x->k - y->k);
//         return x->p >= y->p;
//     }
//     void add(ll k, ll m, int i) {
//         auto z = insert({k, m, 0, i}), y = z++, x = y;
//         while (isect(y, z)) z = erase(z);
//         if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
//         while ((y = x) != begin() && (--x)->p >= y->p)
//             isect(x, erase(y));
//     }
//     pair<ll, ll> query(ll x) {
//         assert(!empty());
//         auto l = *lower_bound(x);
//         return {l.k * x + l.m, l.num};
//     }
// };

namespace geo {
    const double EPS = 1e-9;
    template <typename T> class point {
        static_assert(is_arithmetic<T>::value, "T must be an arithmetic type");
    public:
        T x, y;
        int ind;
        point() : x(T{}), y(T{}), ind(0) {}
        point(const T &_x, const T &_y) : x(_x), y(_y) {}
        point(const T &_x, const T &_y, const int &_i) : x(_x), y(_y), ind(_i) {}
        template <typename S> operator point<S>() const {
            return point<S>(static_cast<S>(x), static_cast<S>(y));
        }
        template <typename S> point &operator=(const point<S> &p) {
            x = p.x;
            y = p.y;
            return *this;
        }
        point &operator+=(const point &p) {
            x += p.x;
            y += p.y;
            return *this;
        }
        point &operator-=(const point &p) {
            x -= p.x;
            y -= p.y;
            return *this;
        }
        point &operator*=(const T &s) {
            x *= s;
            y *= s;
            return *this;
        }
        void swap(point &p) {
            swap(x, p.x);
            swap(y, p.y);
        }
    };
    template <typename T> point<T> make_point(const T &x, const T &y) {
        return point<T>(x, y);
    }
    template <typename T> void swap(point<T> &p, point<T> &q) { p.swap(q); }
    template <typename T> point<T> operator-(const point<T> &p) {
        return point<T>(-p.x, -p.y);
    }
    template <typename T> point<T> operator+(point<T> p, const point<T> &q) {
        return p += q;
    }
    template <typename T> point<T> operator-(point<T> p, const point<T> &q) {
        return p -= q;
    }
    template <typename T> point<T> operator*(point<T> p, const T &s) { return p *= s; }
    template <typename T> point<T> operator*(const T &s, point<T> p) { return p *= s; }
    template <typename T> T cross(const point<T> &p, const point<T> &q) {
        long double ret = (long double)p.x * q.y - (long double)p.y * q.x;
        if (abs(ret) > 1e18) return ret > 0 ? 1 : -1;
        return p.x * q.y - p.y * q.x;
    }
    template <typename T> T operator^(const point<T> &p, const point<T> &q) {
        return cross(p, q);
    }
    template <typename T> bool operator==(const point<T> &p, const point<T> &q) {
        if constexpr (is_integral<T>::value) return p.x == q.x && p.y == q.y;
        else return abs(p.x - q.x) <= EPS && abs(p.y - q.y) <= EPS;
    }
    template <typename T> bool operator!=(const point<T> &p, const point<T> &q) {
        return !(p == q);
    }
    template <typename T> bool operator<(const point<T> &p, const point<T> &q) {
        return p.x < q.x || (p.x == q.x && p.y < q.y);
    }
    template <typename T> bool operator>(const point<T> &p, const point<T> &q) {
        return q < p;
    }
    template <typename T> bool operator<=(const point<T> &p, const point<T> &q) {
        return !(p > q);
    }
    template <typename T> bool operator>=(const point<T> &p, const point<T> &q) {
        return !(p < q);
    }
}  // namespace geo


struct monotonic_dp_hull {
	long long prev_x = LLONG_MIN, prev_y = 1;
	deque<geo::point<long long>> points;
	void add(const geo::point<long long> &p) {
		assert(points.empty() || p.x >= points.back().x);
		if (!points.empty() && p.x == points.back().x) {
			if (p.y <= points.back().y) return;
			points.pop_back();
		}
		while (size() >= 2 &&
		       ((points.back() - p) ^ (points[size() - 2] - points.back())) <= 0)
			points.pop_back();
		points.push_back(p);
	}
	void add(long long m, long long b, int ind) { add(geo::point(m, b, ind)); }
	pair<long long, int> query(long long x, long long y = 1) {
		assert(size() > 0);
		assert(prev_x == LLONG_MIN || x * prev_y >= prev_x * y);
		prev_x = x, prev_y = y;
		while (size() >= 2 &&
		       x * (points[1].x - points[0].x) >= (points[0].y - points[1].y) * y)
			points.pop_front();
		return {points[0].x * x + points[0].y * y, points[0].ind};
	}
	void clear() {
		points.clear();
		prev_x = LLONG_MIN, prev_y = 1;
	}
	int size() const { return points.size(); }

};

int main()
{
	// ifstream cin("input.txt");
    // ofstream cout("output.txt");
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, k; cin >> n >> k;
    vector<ll> a(n + 1), p(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    vector<ll> dp(n + 1, 0), ndp(n + 1, 0);
    vector<vector<int>> opt(k + 1, vector<int>(n + 1));
    for (int ki = 1; ki <= k; ki++) {
        monotonic_dp_hull cht;
        cht.add(p[ki], dp[ki] - p[ki] * p[ki], ki);
        for (int i = ki + 1; i <= n; i++) {
            auto [v, ind] = cht.query(p[i]);
            ndp[i] = v;
            opt[ki][i] = ind;
            cht.add(p[i], dp[i] - p[i] * p[i], i);
        }
        swap(dp, ndp);
    }
    cout << dp[n] << '\n';
    int cur = n, ki = k;
    while(ki) {
        if (opt[ki][cur]) cout << opt[ki][cur] << ' ';
        cur = opt[ki--][cur];
    }
}

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