제출 #243767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243767		islingr	수열 (APIO14_sequence)	C++14	0 / 100	45 ms	7544 KiB

sequence

#include <iostream>
#include <cassert>
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;
const int64_t inf = 1e18;
int64_t f[2][N], a[N];
int opt[K][N], st[N];

void solve(int k, int l, int r, int optl, int optr) {
	if (r < l) return;
	int i = (l + r) / 2;

	f[k & 1][i] = -inf;
	for (int j = optl; j <= min(i, optr); ++j)
		if (ckmax(f[k & 1][i], f[k & 1 ^ 1][j] + a[j] * (a[i] - a[j])))
			opt[k][i] = j;
	solve(k, l, i - 1, optl, opt[k][i]);
	solve(k, i + 1, r, opt[k][i], optr);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, k; cin >> n >> k;

	f[0][0] = -inf;
	for (int i = 1; i <= n; ++i)
		cin >> a[i], a[i] += a[i - 1];
	
	for (int l = 1; l <= k; ++l)
		solve(l, l, n, l, n);

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

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'void solve(int, int, int, int, int)':
sequence.cpp:18:30: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   if (ckmax(f[k & 1][i], f[k & 1 ^ 1][j] + a[j] * (a[i] - a[j])))
                            ~~^~~

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