Submission #639910

#	Time	Username	Problem	Language	Result	Execution time	Memory
639910		bojackduy	Split the sequence (APIO14_sequence)	C++14	0 / 100	68 ms	86116 KiB

sequence

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <functional>
#define task ""
#define size() size() * 1ll 
#define all(x) (x).begin(), (x).end()
#define allr(x, sz) (x) + 1, (x) + 1 + sz
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define numbit(x) __builtin_popcountll(x)

using namespace std;

const int N = 1e5 + 5;
const int M = 1e3 + 1;
const long long mod = 1e9 + 7;
const long long oo = 1e18 + 7;

typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;

template<class t>
bool mini(t &x,t y) {
    if (y < x) {
       x = y;
       return 1;
    }
return 0;
}
template<class t>
bool maxi(t &x,t y) {
    if (x < y) {
       x = y;
       return 1;
    }
return 0;
}
void file() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen(task".inp", "r", stdin);
    // freopen(task".out", "w", stdout);
return ;
}

int n, k;
int a[N], trace[N][202];
ll suf[N], pre[N];
void solve(int test = -1) {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    for (int i = n; i >= 1; i--) suf[i] = suf[i + 1] + a[i];
    auto y = [&](array<ll, 3> &d, int x) -> int {
        return d[0] * x + d[1];
    };
    auto inters = [&](array<ll, 3> &d, array<ll, 3> &d1) -> long double {
        return (long double) (d1[1] - d[1]) / (d[0] - d1[0]);
    };
    deque<array<ll, 3>> dp1;
    for (int i = 1; i <= n; i++) dp1.pb({-pre[i], pre[i] * suf[i + 1], i});
    for (int z = 1; z <= k; z++) {
        deque<array<ll, 3>> dp2;
        for (int i = z + 1; i <= n; i++) {
            while (dp1.size() >= 2 && dp1[1][2] < i && y(dp1[0], suf[i + 1]) <= y(dp1[1], suf[i + 1])) dp1.pop_front();
            int val = y(dp1.front(), suf[i + 1]) + pre[i] * suf[i + 1];
            trace[i][z] = dp1.front()[2];
            if (i == n && z == k) cout << val << '\n';
            if (i < n) {
                array<ll, 3> d = {-pre[i], val, i};
                while (dp2.size() >= 2 && inters(d, dp2.back()) >= inters(dp2.back(), dp2[dp2.size() - 2])) dp2.pop_back();
                dp2.pb(d);
            }
        }
        dp1 = dp2;
    }
    while (k > 0) {
        n = trace[n][k];
        cout << n << ' ';
        k--;
    }
}

int32_t main()  {
    file();
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
return 0;
}
/*
*/

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