Submission #243997

#	Time	Username	Problem	Language	Result	Execution time	Memory
243997		islingr	Split the sequence (APIO14_sequence)	C++14	100 / 100	517 ms	81320 KiB

sequence

#pragma GCC optimize("O3, fast-math")
#include <iostream>
using namespace std;
 
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
const int N = 1e5 + 5, K = 205;
int64_t f[2][N], a[N];
int opt[K][N], s[N];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n; ++i) cin >> a[i], a[i] += a[i - 1];
	for (int l = 1; l <= k; ++l) {
		auto c = [&](int j) { return f[(l & 1) ^ 1][j] - a[j] * a[j]; };
		auto val = [&](int j, int x) { return a[j] * x + c(j); };
		auto cross = [&](int i, int j, int k) {
			return (c(k) - c(i)) * (a[j] - a[i]) - (c(j) - c(i)) * (a[k] - a[i]);
		};
		int t = 0;
		for (int j = l; j <= n; ++j) {
			while (t > 1 && 0 <= cross(s[t - 1], s[t], j)) --t;
			s[++t] = j;
		}
		for (int i = l + 1, j = 1; i <= n; ++i) {
			while (s[j] < i && j < t && val(s[j], a[i]) < val(s[j + 1], a[i])) ++j;
			opt[l][i] = s[j];
			f[l & 1][i] = val(s[j], a[i]);
		}
	}
	cout << f[k & 1][n] << '\n';
	for (int v = n, l = k; v = opt[l--][v]; ) s[l] = v;
	for (int l = 0; l < k; ++l) cout << s[l] << ' ';
}

Compilation message (stderr)

sequence.cpp:1:37: warning: bad option '-f fast-math' to pragma 'optimize' [-Wpragmas]
 #pragma GCC optimize("O3, fast-math")
                                     ^
sequence.cpp:5:46: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]
 template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
                                              ^
sequence.cpp:11:13: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]
 signed main() {
             ^
sequence.cpp: In function 'int main()':
sequence.cpp:18:21: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]
   auto c = [&](int j) { return f[(l & 1) ^ 1][j] - a[j] * a[j]; };
                     ^
sequence.cpp:19:30: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]
   auto val = [&](int j, int x) { return a[j] * x + c(j); };
                              ^
sequence.cpp:20:39: warning: bad option '-f fast-math' to attribute 'optimize' [-Wattributes]
   auto cross = [&](int i, int j, int k) {
                                       ^
sequence.cpp:35:27: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  for (int v = n, l = k; v = opt[l--][v]; ) s[l] = v;
                         ~~^~~~~~~~~~~~~

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