Submission #967239

#	Time	Username	Problem	Language	Result	Execution time	Memory
967239		SmuggingSpun	Split the sequence (APIO14_sequence)	C++14	100 / 100	1095 ms	82184 KiB

sequence

#include<bits/stdc++.h>
#define taskname "sequence"
using namespace std;
typedef long long ll;
template<class T>bool minimize(T& a, T b){
	if(a > b){
		a = b;
		return true;
	}
	return false;
}
const ll INF = 1e18;
const int lim = 1e5 + 5;
const int lim_k = 201;
int n, k, a[lim], f[lim], opt[lim_k][lim];
ll f_square[lim], dp[2][lim];
bool cur = true, pre = false;
ll square(int x){
	return 1LL * x * x;
}
ll cost(int l, int r){
	return (square(f[r] - f[l - 1]) - f_square[r] + f_square[l - 1]) >> 1LL;
}
void solve(const int id, int l, int r, int opt_l, int opt_r){
	if(l > r){
		return;
	}
	int m = (l + r) >> 1;
	dp[cur][m] = INF;
	for(int i = min(m, opt_r); i >= opt_l; i--){
		if(minimize(dp[cur][m], dp[pre][i - 1] + cost(i, m))){
			opt[id][m] = i;
		}
	}
	solve(id, l, m - 1, opt_l, opt[id][m]);
	solve(id, m + 1, r, opt[id][m], opt_r);
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> k;
	f[0] = dp[cur][0] = f_square[0] = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		dp[cur][i] = (square(f[i] = f[i - 1] + a[i]) - (f_square[i] = f_square[i - 1] + square(a[i]))) >> 1LL;
	}
	for(int i = 0; i < k; i++){
		swap(cur, pre);
		for(int j = i + 1; j > 0; j--){
			dp[cur][j] = 0;
		}
		solve(i, i + 2, n, i + 2, n);
	}
	cout << cost(1, n) - dp[cur][n] << "\n";
	vector<int>cut_point;
	for(int i = k - 1, vertex = n; i > -1; i--){
		cut_point.emplace_back(vertex = opt[i][vertex] - 1);
	}
	for(int i = k - 1; i > -1; i--){
		cout << cut_point[i] << " ";
	}
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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