Submission #1248833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248833		JelalTkm	Split the sequence (APIO14_sequence)	C++20	71 / 100	313 ms	196608 KiB

sequence

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define ll long long int
#define ld long double

const int N = 1e5 + 10;
const int md = 1e9 + 7;
// const int INF = 1e18;

struct node {
    ll k, b;
    int ind;
};

struct CHT {
  deque<node> hull;
  ll f(pair<ll, ll> line, ll x) {
    return line.first * x + line.second;
  }
  int lefff = 0;
  pair<ll, int> get(ll x) {
    while ((lefff + 1) < (int) hull.size() && f({hull[lefff].k, hull[lefff].b}, x) <= f({hull[lefff + 1].k, hull[lefff + 1].b}, x)) {
        lefff++;
    }
 
    return {f({hull[lefff].k, hull[lefff].b}, x), hull[lefff].ind};
  }
  ld intersect(ll k1, ll b1, ll k2, ll b2) {
    return (ld)(b2 - b1) / (ld)(k1 - k2);
  }
  ld intersect(pair<ll, ll> line1, pair<ll, ll> line2) {
    return intersect(line1.first, line1.second, line2.first, line2.second);
  }
  void add(ll k, ll b, int ind) {
    pair<ll, ll> line = pair<ll, ll> (k, b);
    while (hull.size() > 1) {
      int s = (int) hull.size();
      if (intersect({hull[s - 2].k, hull[s - 2].b}, line) <= intersect({hull[s - 2].k, hull[s - 2].b}, {hull[s - 1].k, hull[s - 1].b})) {
        hull.pop_back();
      }
      else break;
    }
 
    hull.push_back({k, b, ind});
  }
};

int dp[N][205];

int32_t main(int32_t argc, char *argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k; k++;
        vector<int> a(n + 1);
        vector<ll> pref(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            pref[i] = pref[i - 1] + a[i];
        }

        vector<CHT> hull(k + 1, CHT());
        // vector<vector<pair<int, int>>> dp(n + 1, vector<pair<int, int>> (k + 1));
        ll res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = min(i, k); j > 1; j--) {
                auto xy = hull[j - 1].get(pref[i]);
                dp[i][j] = xy.second;
                hull[j].add(pref[i], -pref[i] * pref[i] + xy.first, i);
                if (i == n && j == k)
                    res = xy.first;
            }
            hull[1].add(pref[i], -pref[i] * pref[i], i);
        }

        cout << res << '\n';

        int i = n, j = k;
        vector<int> ans;
        while (j != 1) {
            i = dp[i][j]; j--;
            ans.push_back(i);
        }

        reverse(ans.begin(), ans.end());
        for (auto i: ans)
            cout << i << " ";
        cout << '\n';
    }

    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