Submission #243739

#	Time	Username	Problem	Language	Result	Execution time	Memory
243739		islingr	Split the sequence (APIO14_sequence)	C++14	28 / 100	2091 ms	4984 KiB

sequence

#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[K][N], a[N], inf = 1e18;
int opt[K][N], st[N];

// opt[l][i] <= opt[l + 1][i]


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];

	f[0][0] = -inf;
	for (int l = 1; l <= k; ++l)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j < i; ++j)
				if (ckmax(f[l][i], f[l - 1][j] + a[j] * (a[i] - a[j])))
					opt[l][i] = j;

	cout << f[k][n] << '\n';
	for (int v = n, l = k; v = opt[l--][v]; ) st[l] = v;
	for (int l = 0; l < k; ++l) cout << st[l] << ' ';
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:29:27: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  for (int v = n, l = k; v = opt[l--][v]; ) st[l] = v;
                         ~~^~~~~~~~~~~~~

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