Submission #716312

#	Time	Username	Problem	Language	Result	Execution time	Memory
716312		Bungmint	Split the sequence (APIO14_sequence)	C++17	100 / 100	692 ms	81860 KiB

sequence

// Copyright © 2022 Youngmin Park. All rights reserved.
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

#pragma region TEMPLATE

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound

constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
const ld PI = acos((ld)-1.0);
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
constexpr bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
constexpr bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } // divide a by b rounded down

#ifdef LOCAL
#include "miscellaneous/debug.h"
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda {
	template <typename Fun>
	struct y_combinator_result {
		Fun fun_;
		template <typename T>
		explicit constexpr y_combinator_result(T &&fun) : fun_(forward<T>(fun)) {}
		template <typename... Args>
		constexpr decltype(auto) operator()(Args &&...args) const {
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun) {
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

#pragma endregion TEMPLATE

struct Line {
    ll m, b;
    int ind;
    ld isect(const Line& other) const {
        return (ld)(b - other.b) / (other.m - m);
    }
    ll eval(ll x) { return m * x + b; };
};

int par[201][100'001];

void solve() {
    int n, k;
    cin >> n >> k;
    vl pref(n), dp(n);
    for (int i = 0; i < n; i++) {
        cin >> pref[i];
        if (i) pref[i] += pref[i - 1];
    } 
    for (int x = 1; x <= k; x++) {
        vl nxt(n, -LINF);
        deque<Line> hull;
        for (int i = 0; i < n; i++) {
            if (dp[i] == -LINF) continue; 
            while (sz(hull) > 1 && hull[0].eval(pref[i]) <= hull[1].eval(pref[i])) {
                hull.pop_front();
            }
            if (sz(hull)) {
                nxt[i] = hull[0].eval(pref[i]);
                par[x][i] = hull[0].ind;
            }
            Line l{pref[i], dp[i] - pref[i] * pref[i], i};
            while (sz(hull) > 1 && end(hull)[-2].isect(l) <= end(hull)[-2].isect(end(hull)[-1])) {
                hull.pop_back();
            }
            hull.pb(l);
        }
        dbg(nxt);
        swap(dp, nxt);
    }
    cout << dp[n - 1] << '\n';
    vi res;
    int cnt = k, pos = n - 1;
    while (true) {
        if (pos != n - 1) res.pb(pos);
        if (cnt == 0) break;
        pos = par[cnt][pos];
        cnt--;
    }
    reverse(all(res));
    for (int i = 0; i < k; i++) cout << res[i] + 1 << " \n"[i == k - 1];

}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--) {
		solve();
	}
#ifdef LOCAL
	cerr << "Time elapsed: " << 1.0 * (double)clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}

Compilation message (stderr)

sequence.cpp:7: warning: ignoring '#pragma region TEMPLATE' [-Wunknown-pragmas]
    7 | #pragma region TEMPLATE
      | 
sequence.cpp:66: warning: ignoring '#pragma endregion TEMPLATE' [-Wunknown-pragmas]
   66 | #pragma endregion TEMPLATE
      | 
sequence.cpp: In function 'void solve()':
sequence.cpp:46:18: warning: statement has no effect [-Wunused-value]
   46 | #define dbg(...) 42
      |                  ^~
sequence.cpp:105:9: note: in expansion of macro 'dbg'
  105 |         dbg(nxt);
      |         ^~~

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