Submission #1039183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039183		june0501	Split the sequence (APIO14_sequence)	C++17	100 / 100	352 ms	87788 KiB

sequence

#include <bits/stdc++.h>
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3,unroll-loops")
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
using namespace std;
using ll [[maybe_unused]] = long long;
using ull [[maybe_unused]] = unsigned long long;
using lll [[maybe_unused]] = __int128;
using lld [[maybe_unused]] = long double;
using llld [[maybe_unused]] = __float128;
#define GRAPH_TYPE_DEFINED
template<typename T> using graph [[maybe_unused]] = vector<vector<pair<int,T>>>;
#define MATRIX_TYPE_DEFINED
template<typename T> using matrix [[maybe_unused]] = vector<vector<T>>;

/**
 *  "Premature optimization is the root of all evil."
 *  <sub> Donald Knuth </sub>
 */

#ifdef ONLINE_JUDGE // Be careful if problem is about strings.
/**
 * Namespace for Fast I/O
 *
 * @class@b INPUT
 * class which can replace the cin
 *
 * @class@b OUTPUT
 * class which can replace the cout
 *
 * @Description
 * These classes use low-level i/o functions (@c fread()/mmap() for input, @c fwrite()/write() for output)
 * so that they can read or write much faster than cin and cout. <br>
 * Several macros are defined for convenience of using them.
 *
 * @Author  <a href="https://blog.naver.com/jinhan814/222266396476">jinhan814</a>
 * @Date    2021-05-06
 */
namespace FastIO {
#include <sys/stat.h>
#include <sys/mman.h>
#include <unistd.h>

    constexpr int SZ = 1 << 20;

    /* Class INPUT */
    class INPUT {
    private:
        char* p;
        bool __END_FLAG__, __GET_LINE_FLAG__; // NOLINT
    public:
        explicit operator bool() const { return !__END_FLAG__; }
        INPUT() {
            struct stat st;
            fstat(0, &st);
            p = (char*)mmap(0, st.st_size, PROT_READ, MAP_SHARED, 0, 0);
        }

        static bool IsBlank(char c) { return c == ' ' || c == '\n'; }

        static bool IsEnd(char c) { return c == '\0'; }

        char _ReadChar() { // NOLINT
            return *p++;
        }

        char ReadChar() {
            char ret = _ReadChar();
            for (; IsBlank(ret); ret = _ReadChar());

            return ret;
        }

        template<class T>
        T ReadInt() {
            T ret = 0;
            char curr = _ReadChar();
            bool minus_flag = false;

            for (; IsBlank(curr); curr = _ReadChar());
            if (curr == '-') minus_flag = true, curr = _ReadChar();
            for (; !IsBlank(curr) && !IsEnd(curr); curr = _ReadChar())
                ret = 10 * ret + (curr & 15);
            if (IsEnd(curr)) __END_FLAG__ = true;

            return minus_flag ? -ret : ret;
        }

        std::string ReadString() {
            std::string ret;
            char curr = _ReadChar();
            for (; IsBlank(curr); curr = _ReadChar());
            for (; !IsBlank(curr) && !IsEnd(curr); curr = _ReadChar())
                ret += curr;
            if (IsEnd(curr)) __END_FLAG__ = true;

            return ret;
        }

        double ReadDouble() {
            std::string ret = ReadString();
            return std::stod(ret);
        }

        std::string getline() {
            std::string ret;
            char curr = _ReadChar();
            for (; curr != '\n' && !IsEnd(curr); curr = _ReadChar())
                ret += curr;
            if (__GET_LINE_FLAG__) __END_FLAG__ = true;
            if (IsEnd(curr)) __GET_LINE_FLAG__ = true;

            return ret;
        }

        friend INPUT &getline(INPUT &in, std::string &s) {
            s = in.getline();
            return in;
        }
    } _in;
    /* End of Class INPUT */

    /* Class OUTPUT */
    class OUTPUT {
    private:
        char writeBuffer[SZ];
        int write_idx;
    public:
        ~OUTPUT() { Flush(); }

        explicit operator bool() const { return true; }

        void Flush() {
            write(1, writeBuffer, write_idx);
            write_idx = 0;
        }

        void WriteChar(char c) {
            if (write_idx == SZ) Flush();
            writeBuffer[write_idx++] = c;
        }

        template<class T>
        void WriteInt(T n) {
            int sz = GetSize(n);
            if (write_idx + sz >= SZ) Flush();
            if (n < 0) writeBuffer[write_idx++] = '-', n = -n;
            for (int i = sz; i-- > 0; n /= 10)
                writeBuffer[write_idx + i] = n % 10 | 48;
            write_idx += sz;
        }

        void WriteString(const std::string& s) {
            for (auto &c: s) WriteChar(c);
        }

        void WriteDouble(double d) {
            WriteString(std::to_string(d));
        }

        template<class T>
        int GetSize(T n) {
            int ret = 1;
            for (n = n >= 0 ? n : -n; n >= 10; n /= 10) ret++;

            return ret;
        }
    } _out;
    /* End of Class OUTPUT */

    /* Operators */
    INPUT &operator>>(INPUT &in, char &i) {
        i = in.ReadChar();
        return in;
    }

    INPUT &operator>>(INPUT &in, std::string &i) {
        i = in.ReadString();
        return in;
    }

    template<class T, typename std::enable_if_t<std::is_arithmetic_v<T>> * = nullptr>
    INPUT &operator>>(INPUT &in, T &i) {
        if constexpr (std::is_floating_point_v<T>) i = in.ReadDouble();
        else if constexpr (std::is_integral_v<T>) i = in.ReadInt<T>();
        return in;
    }

    OUTPUT &operator<<(OUTPUT &out, char i) {
        out.WriteChar(i);
        return out;
    }

    OUTPUT &operator<<(OUTPUT &out, const std::string &i) {
        out.WriteString(i);
        return out;
    }

    template<class T, typename std::enable_if_t<std::is_arithmetic_v<T>> * = nullptr>
    OUTPUT &operator<<(OUTPUT &out, T i) {
        if constexpr (std::is_floating_point_v<T>) out.WriteDouble(i);
        else if constexpr (std::is_integral_v<T>) out.WriteInt(i);
        return out;
    }

    /* Macros for convenience */
    #undef fastIO
    #define fastIO 1
    #define cin _in
    #define cout _out
    #define istream INPUT
    #define ostream OUTPUT
};
using namespace FastIO;
#endif

/**
 * Convex Hull Trick implementation
 * @tparam Comp default to be std::greater which means query gives minimum value
 */
template<typename Comp = std::greater<>>
class ConvexHullTrick {
    Comp comp;

    struct Fraction {
        // a / b
        ll a, b;
        Fraction(ll a, ll b) : a(a), b(b) {
            if (b < 0) a = -a, b = -b;
        }
        Fraction(ll a) : a(a), b(1) {} // NOLINT(implicit conversion)
        bool operator< (const Fraction &other) const {
            return (lll) a * other.b < (lll) b * other.a;
        }
        bool operator== (const Fraction &other) const {
            return (lll) a * other.b == (lll) b * other.a;
        }
        bool operator<= (const Fraction &other) const {
            return (*this == other) || (*this < other);
        }
        bool operator> (const Fraction &other) const {
            return !(*this <= other);
        }
        bool operator>= (const Fraction &other) const {
            return !(*this < other);
        }
    };

    struct Line : public Fraction {
        // f(x) = ax + b
        Line(ll a, ll b) : Fraction(a, b) {}
    };

    [[nodiscard]] // return the value of f(x) = ax + b
    ll get_value(const Line& f, const ll x) const { return f.a * x + f.b; }

    [[nodiscard]] // return the x pos of the intersection of the two given lines
    Fraction get_cross_x(const Line& l1, const Line& l2) const {
        // a1 x + b1 = a2 x + b2 -> (a1 - a2)x = (b2 - b1)
        return {l2.b - l1.b, l1.a - l2.a};
    }

    [[nodiscard]] // return cross_x(l1, l2) > cross_x(l2, l3)
    bool compare_cross(const Line& l1, const Line& l2, const Line& l3) const {
        return get_cross_x(l1, l2) > get_cross_x(l2, l3);
    }

    std::vector<pair<Line,int>> lines; // maintain the hull

public:
    void insert(ll a, ll b, int idx) {
        Line newLine(a, b);
        for (int sz = (int)lines.size(); sz > 1; sz--) {
            if (a == lines.back().first.a && b >= lines.back().first.b
            || compare_cross(lines[sz - 2].first, lines[sz - 1].first, newLine)) lines.pop_back();
            else break;
        }
        lines.emplace_back(newLine, idx);
    }

    pair<ll,int> query(ll x) {
        int l = 0, r = lines.size() - 1;
        while (l != r) {
            int m = (l + r) >> 1;
            if (comp(get_value(lines[m].first, x), get_value(lines[m+1].first, x))) l = m + 1;
            else r = m;
        }
        return {get_value(lines[l].first, x), lines[l].second};
    }

    // only can be used when x is monotonically increasing
    int ptr = 0;
    pair<ll,int> query_monotonic(ll x) {
        while (ptr + 1 < lines.size() && comp(get_value(lines[ptr].first, x), get_value(lines[ptr + 1].first, x))) ptr++;
        return {get_value(lines[ptr].first, x), lines[ptr].second};
    }

    void clear() {
        lines.clear();
        ptr = 0;
    }
};

int32_t main() {
    fastIO;
    int n, K;
    cin >> n >> K;
    vector<ll> v(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> v[i], v[i] += v[i-1];

    // dp[k][i] := max val when covers 1 to i with k slices
    // dp[k][i] = max_{j < i}(dp[k-1][j] + (prefix[i] - prefix[j]) * prefix[j])
    // Let y(k) = dp[k][i], x = prefix[i],
    // then, y(k) = prefix[j] * x - prefix[j]^2 + dp[k-1][j]

    matrix<ll> dp(2, vector<ll>(n + 1, 0));
    matrix<int> rev(K + 1, vector<int>(n + 1));
    ConvexHullTrick<less_equal<>> CHT;
    for (int k = 1; k <= K; k++) {
        CHT.clear();
        for (int i = 1; i < n; i++) {
            CHT.insert(v[i], dp[0][i] - v[i] * v[i], i);
            tie(dp[1][i + 1], rev[k][i + 1]) = CHT.query_monotonic(v[i+1]);
        }
        swap(dp[0], dp[1]);
    }
    cout << dp[0][n] << endl;

    vector<int> ans;
    for (int k = K, i = n; k > 0; k--) {
        ans.emplace_back(i = rev[k][i]);
    }
    reverse(all(ans));
    for (const auto &e : ans) cout << e << ' ';

    return 0;
}

Compilation message (stderr)

sequence.cpp: In instantiation of 'void ConvexHullTrick<Comp>::insert(ll, ll, int) [with Comp = std::less_equal<void>; ll = long long int]':
sequence.cpp:325:55:   required from here
sequence.cpp:277:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  277 |             if (a == lines.back().first.a && b >= lines.back().first.b
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp: In instantiation of 'std::pair<long long int, int> ConvexHullTrick<Comp>::query_monotonic(ll) [with Comp = std::less_equal<void>; ll = long long int]':
sequence.cpp:326:74:   required from here
sequence.cpp:297:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<ConvexHullTrick<std::less_equal<void> >::Line, int>, std::allocator<std::pair<ConvexHullTrick<std::less_equal<void> >::Line, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  297 |         while (ptr + 1 < lines.size() && comp(get_value(lines[ptr].first, x), get_value(lines[ptr + 1].first, x))) ptr++;
      |                ~~~~~~~~^~~~~~~~~~~~~~

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