Submission #1207906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207906		A_M_Namdar	Split the sequence (APIO14_sequence)	C++20	50 / 100	386 ms	149152 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

const long long N = 1e4 + 10, M = 200 + 10;
long long n, k, a[N], dp[N][M], ps[N];
int par[N][M];
set<pair<long long, long long>> s[M];

void add_line(long long i, long long j) {
	while (!s[j].empty()) {
		pair<long long, long long> tmp = *(--s[j].end());
		if (dp[tmp.second][j] + ps[tmp.second] * (tmp.first - ps[tmp.second]) <= dp[i][j] + ps[i] * (tmp.first - ps[i])) 
			s[j].erase(--s[j].end());
		else 
			break;
	}
	if (s[j].empty()) 
		s[j].insert({0, i});
	else {
		pair<long long, long long> tmp = *(--s[j].end());
		long long x = (-dp[i][j] + dp[tmp.second][j] + (ps[i] * ps[i]) - (ps[tmp.second] * ps[tmp.second])) / (-ps[tmp.second] + ps[i]);
		x +=         ((-dp[i][j] + dp[tmp.second][j] + (ps[i] * ps[i]) - (ps[tmp.second] * ps[tmp.second])) % (-ps[tmp.second] + ps[i]) > 0);
		s[j].insert({x, i});
//		cout << x << "          " << i << " : \n";
//		cout << (-dp[i][j] + dp[tmp.second][j] + (ps[i] * ps[i]) - (ps[tmp.second] * ps[tmp.second])) << ' ' <<  (ps[tmp.second] - ps[i]) << '\n';
	}
}

pair<long long, long long> get(long long j, long long x) {
	auto it = s[j].lower_bound({x + 1, -1});
	it--;
//	cout << x << ' ' << it->first << ' ' << it->second << ' ' << dp[it->second][j] << ' ' << ps[it->second]  << ' ' <<  (x - ps[it->second]) << ' ' << '\n';
	return make_pair(dp[it->second][j] + ps[it->second] * (x - ps[it->second]), it->second);
}

void input() {
	cin >> n >> k;
	for (long long i = 0; i < n; i++) {
		cin >> a[i];
		ps[i + 1] = ps[i] + a[i];
//		cout << i + 1 << " : " << ps[i + 1] << '\n';
	}
}

void solve() {
	memset(dp, -63, sizeof dp);
	for (long long i = 1; i <= n; i++) {
		dp[i][1] = 0;
		par[i][0] = 0;
	}
	for (long long j = 2; j <= k + 1; j++) {
		add_line(j - 1, j - 1);
		for (long long i = j; i <= n; i++) {
			pair<long long, long long> tmp = get(j - 1, ps[i]);
			dp[i][j] = tmp.first;
			par[i][j] = tmp.second;
//			cout << i << ' ' << j << ' ' << dp[i][j] << endl;
			add_line(i, j - 1);
		}
	}
	cout << dp[n][k + 1] << '\n';
	long long p = par[n][k + 1], q = k;
	while (p > 0) {
		cout << p << ' ';
		p = par[p][q];
		q--;
	}
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	solve();
}

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