Submission #778028

#	Time	Username	Problem	Language	Result	Execution time	Memory
778028		horiiseun	Split the sequence (APIO14_sequence)	C++17	100 / 100	684 ms	90204 KiB

sequence

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <random>
#include <string>
#include <bitset>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define ll long long
#define f first
#define s second
 
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
 
template<typename A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);
 
template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
 
template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}
 
template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
 
template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
 
template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
void _print() { cerr << "]\n"; }
 
template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}
 
#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
    #define D(...)
#endif
 
const double EPS = numeric_limits<double>::epsilon();
 
struct Line {
    ll m;
    ll c;
    double p; 
    int ct;
};
 
struct CHT {
    vector<Line> lines;
    int k;
 
    double getX(ll m1, ll c1, ll m2, ll c2) {
        return (double) (c1 - c2) / (double) (m2 - m1 + EPS);
    }
 
    void addLine(ll m, ll c, int ct) {
        double p = LLONG_MIN;
        while (!lines.empty()) {
            p = getX(m, c, lines.back().m, lines.back().c);
            if (p < lines.back().p - EPS) lines.pop_back();
            else break;
        }
        lines.push_back({m, c, p, ct});
    }
 
    pair<ll, int> getY(ll x) {
        int l = 0, r = lines.size() - 1, ret = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            if (lines[m].p <= x + EPS) {
                ret = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return {lines[ret].m * x + lines[ret].c, lines[ret].ct};
    }
 
    pair<ll, int> getYFast(ll x) {
        k = min(k, (int) lines.size() - 1);
        while (k + 1 < lines.size() && lines[k + 1].p <= x + EPS) {
            k++;
        }
        return {lines[k].m * x + lines[k].c, lines[k].ct};
    }
 
    CHT() {}
 
    void init() {
        lines.clear();
        k = 0;
    }
};
 
int n, k, a[100005], from[100005][205], idx;
ll dp[100005][2], pref[100005], mx;
vector<int> path;
CHT *chc, *chp;
 
void prnt(int pos, int ct) {
    if (ct == 1) return;
    prnt(from[pos][ct], ct - 1);
    cout << from[pos][ct] << " ";
}
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = a[i];
        pref[i] += pref[i - 1];
    }
 
    if (n <= 1000) {
        for (int i = 1; i <= n; i++) {
            dp[i][1] = pref[i] * (pref[n] - pref[i]);
        }
        for (int i = 2; i <= k + 1; i++) {
            for (int j = i; j <= n; j++) {
                for (int m = 1; m < j; m++) {
                    if (dp[j][i % 2] <= dp[m][(i + 1) % 2] + (pref[j] - pref[m]) * (pref[n] - pref[j])) {
                        dp[j][i % 2] = dp[m][(i + 1) % 2] + (pref[j] - pref[m]) * (pref[n] - pref[j]);
                        from[j][i] = m;
                    }
                }
            }
        }
        cout << dp[n][(k + 1) % 2] << "\n";
    } else {
        chc = new CHT(), chp = new CHT();
        for (int i = 1; i <= n; i++) {
            dp[i][1] = pref[i] * (pref[n] - pref[i]);
            chp->addLine(pref[i], dp[i][1] - pref[i] * pref[n], i);
        }
        for (int i = 2; i <= k + 1; i++) {
            for (int j = i; j <= n; j++) {
                pair<ll, int> curr = chp->getYFast(pref[j]);
                dp[j][i % 2] = curr.f + (pref[n] - pref[j]) * pref[j];
                from[j][i] = curr.s;
                chc->addLine(pref[j], dp[j][i % 2] - pref[j] * pref[n], j);
            }
            chp->init();
            swap(chp, chc);
        }
        cout << dp[n][(k + 1) % 2] << "\n"; 
    }
    prnt(n, k + 1);
 
}

Compilation message (stderr)

sequence.cpp: In member function 'std::pair<long long int, int> CHT::getYFast(long long int)':
sequence.cpp:158:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         while (k + 1 < lines.size() && lines[k + 1].p <= x + EPS) {
      |                ~~~~~~^~~~~~~~~~~~~~

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