Submission #549165

#	Time	Username	Problem	Language	Result	Execution time	Memory
549165		Zanite	Split the sequence (APIO14_sequence)	C++17	100 / 100	1039 ms	87280 KiB

sequence

// "I assure you that you guys won't make it to the top 4"
// - Tzaph, 21 December 2021

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ll long long
#define ld long double
#define si short int
#define i8 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define psi pair<si, si>
#define pi8 pair<i8, i8>
#define pq priority_queue
#define fi first
#define se second

#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'

#define yume using
#define wo namespace
#define kanaeyo std

yume wo kanaeyo;

template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
 
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
 
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}

const ll ModA = 998244353;
const ll ModC = 1e9 + 7;
const ll INF = 1e18;
const ll iINF = 1e9;

const ld EPS = 1e-9;
const ld iEPS = 1e-6;

struct Line {
	ll m, c;

	Line(ll _m, ll _c) : m(_m), c(_c) {}

	ld intersect(const Line &other) const {
		return (ld)(other.c - c) / (ld)(m - other.m);
	}

	ll operator() (ll x) {
		return 1ll * m * x + c;
	}
};

struct ConvexHull {
	// lines are inserted in non-decreasing order of slopes
	// maintains max hull

	vector<pair<ll, Line>> hull;

	ConvexHull() {}

	void insert(pair<ll, Line> cur) {
		while (!hull.empty()) {
			if (hull.back().se.m == cur.se.m) {
				if (hull.back().se.c < cur.se.c) {
					hull.pop_back();
				} else return;
			} else break;
		}

		while (hull.size() >= 2) {
			int hs = hull.size();
			if (hull[hs-2].se.intersect(hull[hs-1].se) >= hull[hs-1].se.intersect(cur.se)) {
				hull.pop_back();
			} else break;
		}

		hull.push_back(cur);
	}
};

const ll maxK = 202, maxN = 1e5 + 1;

ll n, k, a[maxN], pf[maxN];
ll dp[2][maxN];
int pred[maxK][maxN];

ll pref(ll l, ll r) {
	return pf[r] - pf[l-1];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> n >> k;
	for (ll i = 1; i <= n; i++) {
		cin >> a[i];
		pf[i] = pf[i-1] + a[i];
	}

	for (ll x = 1; x <= k; x++) {
		int cur = x & 1, prv = cur ^ 1;

		// insert previous DP into CH
		ConvexHull CH = ConvexHull();
		for (ll i = 1; i <= n; i++) {
			CH.insert({i, Line(pf[i], dp[prv][i] - 1ll * pf[i] * pf[i])});
			//printf("!%lld %lld\n", pf[i], dp[x-1][i] - 1ll * pf[i] * pf[i]);
		}

		for (auto i : CH.hull) {
			//printf("%lld %lld\n", i.se.m, i.se.c);
		}

		for (ll i = 1; i < x; i++) {
			dp[cur][i] = -INF;

			//printf("dp[%lld][%lld] = %lld\n", x, i, dp[x][i]);
		}

		for (ll i = x, ptr = 0; i <= n; i++) {
			while (ptr != CH.hull.size()-1 && CH.hull[ptr].se.intersect(CH.hull[ptr+1].se) < pf[i] && CH.hull[ptr+1].fi < i) {
				ptr++;
			}
			if (CH.hull[ptr].fi >= i) {
				dp[cur][i] = -INF;
			} else {
				dp[cur][i] = CH.hull[ptr].se(pf[i]);
				pred[x][i] = CH.hull[ptr].fi;
			}
			//printf("dp[%lld][%lld] = %lld\n", x, i, dp[x][i]);
		}
	}

	cout << dp[k & 1][n] << '\n';
	for (ll i = k, cur = n; i > 0; i--) {
		cout << pred[i][cur] << ' ';
		cur = pred[i][cur];
	}
	cout << '\n';
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:124:13: warning: variable 'i' set but not used [-Wunused-but-set-variable]
  124 |   for (auto i : CH.hull) {
      |             ^
sequence.cpp:135:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, Line> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |    while (ptr != CH.hull.size()-1 && CH.hull[ptr].se.intersect(CH.hull[ptr+1].se) < pf[i] && CH.hull[ptr+1].fi < i) {
      |           ~~~~^~~~~~~~~~~~~~~~~~~

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