제출 #673902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
673902		KiriLL1ca	수열 (APIO14_sequence)	C++17	71 / 100	202 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 ll inf = 1e18 + 127;

inline void solve () {
        int n, k; cin >> n >> k; ++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, -inf));
        vector <vector <int>> par (n + 1, vector <int> (k + 1));

        function <ll(int, int)> cost = [&] (int l, int r) { return (sum - p[r]) * (p[r] - p[l - 1]); };
        function <void(int, int, int, int, int)> dc = [&] (int l, int r, int optl, int optr, int lay) {
                if (l > r) return;
                int mid = (l + r) >> 1;
                pair <ll, int> opt = {-inf, -1};
                for (int i = optl; i <= min(mid, optr); ++i) umax(opt, mp(dp[i - 1][lay - 1] + cost(i, mid), i));
                dp[mid][lay] = opt.fr;
                par[mid][lay] = opt.sc - 1;
                dc(l, mid - 1, optl, opt.sc, lay);
                dc(mid + 1, r, opt.sc, optr, lay);
        };

        for (int i = 1; i <= n; ++i) dp[i][1] = cost(1, i);
        for (int i = 2; i <= k; ++i) dc(i, n, 1, n, i);

        vector <int> res;
        int id = n;
        for (int i = k; i >= 2; --i) {
                id = par[id][i];
                assert(id != -1);
                res.pb(id);
        }
        reverse(all(res));
        cout << dp[n][k] << 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;
}

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