Submission #416233

#	Time	Username	Problem	Language	Result	Execution time	Memory
416233		DEQK	Split the sequence (APIO14_sequence)	C++17	100 / 100	1653 ms	81376 KiB

sequence

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 1e5 + 5, K = 205; 
const ll INF = numeric_limits<ll>::max();
int n, k;
ll a[N];
ll dp[N][2];
int p[K][N];
int opt[N];
ll cost(int i,int j) {
	assert(j < i);
	return dp[j][0] + a[j] * (a[i] - a[j]);
}
void solve(int l,int r,int tl,int tr) {
	if(l > r) return;
	int m = l + r >> 1;
	opt[m] = -1;
	for(int j = tl; j <= min(m - 1, tr); ++j) {
		if(opt[m] == -1 || cost(m, opt[m]) < cost(m, j)) {
			opt[m] = j;
		}
	}
	if(opt[m] == -1) {
		dp[m][1] = -INF;
	} else {
		dp[m][1] = cost(m, opt[m]);
	}
	solve(l, m - 1, tl, opt[m]);
	solve(m + 1, r, opt[m], tr);
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	for(int j = 1; j <= k; j++) {
		dp[0][0] = -INF;
		for(int i = 1; i <= n; i++) {
			dp[i][0] = dp[i][1];
		}
		solve(1, n, 1, n);
		for(int i = 1; i <= n; ++i) {
			p[j][i] = opt[i];
		}
	}
	cout << dp[n][1] << "\n";
	vector<int> ans; 
	for(int i = k, cur = n; i; i--) {
		ans.push_back(p[i][cur]); 
		cur = p[i][cur]; 
	}
	for(int i = (int)ans.size() - 1; i >= 0; i--) if(ans[i]) cout << ans[i] << " ";
}

Compilation message (stderr)

sequence.cpp: In function 'void solve(int, int, int, int)':
sequence.cpp:18:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |  int m = l + r >> 1;
      |          ~~^~~

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