Submission #673608

#	Time	Username	Problem	Language	Result	Execution time	Memory
673608		KiriLL1ca	Split the sequence (APIO14_sequence)	C++17	11 / 100	145 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define mp make_pair
#define vec vector

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int INF = 1e18 + 127;
const ld EPS = 1e-5;

struct line {
        ll k = 0, b = INF;
        int id = -1;
        line () {}
        line (ll k, ll b, int id) : k(k), b(b), id(id) {}
        inline ll operator () (const ll &x) { return k * x + b; }
};

struct cht {
        vector <line> s;
        vector <ld> pt;
        inline ld cross (const line &a, const line &b) { return (ld)(b.b - a.b) / (ld)(a.k - b.k + EPS); }
        inline void add (const line &x) {
                while (sz(s) && cross(s.back(), x) <= pt.back()) s.pop_back(), pt.pop_back();
                if (!sz(s)) pt.pb(-INF);
                else pt.pb(cross(s.back(), x));
                s.pb(x);
        }
        inline line get (const ll &x) { return s[upper_bound(all(pt), x) - pt.begin() - 1]; }
};

inline ll sqr (const ll &x) { return x * x; }

/// dp[i][k] = dp[j-1][k-1] + (p[i] - p[j-1]) * (s - p[i])
///          = (p[i]*s - p[i]*p[i]) + dp[j-1][k-1] - s*p[j-1] + p[i]*p[j-1]

inline void solve () {
        int n, k; cin >> n >> k;
        vector <ll> a (n + 1), p (n + 1);
        ll sum = 0;
        for (int i = 1; i <= n; ++i) cin >> a[i], sum += a[i];
        for (int i = 1; i <= n; ++i) p[i] = p[i - 1] + a[i];

        vector <vector <ll>> dp (n + 1, vector <ll> (k + 1));
        vector <vector <int>> par (n + 1, vector <int> (k + 1));

        for (int i = 1; i <= n; ++i) dp[i][1] = p[i] * (sum - p[i]);
        for (int b = 2; b <= k; ++b) {
                cht orz;
                for (int i = 1; i < b; ++i) {
                        orz.add(line(p[i - 1], dp[i - 1][b - 1] - sum * p[i - 1], i - 1));
                }
                for (int i = b; i <= n; ++i) {
                        orz.add(line(p[i - 1], dp[i - 1][b - 1] - sum * p[i - 1], i - 1));
                        line opt = orz.get(p[i]);
                        dp[i][b] = p[i] * sum - sqr(p[i]) + opt(p[i]);
                        par[i][b] = opt.id;
                }
        }


        pair <ll, int> mx = {-1, -1};
        for (int i = k; i <= n; ++i) umax(mx, {dp[i][k], i});
        vector <int> res;
        int og = mx.sc, ogg = k;
        while (og > 0) {
                res.pb(og);
                og = par[og][ogg--];
        }
        reverse(all(res));
        cout << mx.fr << endl;
        for (auto i : res) cout << i << " ";
}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #ifdef LOCAL
                freopen("input.txt", "r", stdin);
                freopen("output.txt", "w", stdout);
        #endif
        int t = 1; // cin >> t;
        while (t--) solve();
        return 0;
}

Compilation message (stderr)

sequence.cpp:29:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0000000000000001e+18' to '2147483647' [-Woverflow]
   29 | const int INF = 1e18 + 127;
      |                 ~~~~~^~~~~

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