Submission #948938

#	Time	Username	Problem	Language	Result	Execution time	Memory
948938		IBory	Split the sequence (APIO14_sequence)	C++17	100 / 100	552 ms	84948 KiB

sequence

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 100007;
int pv[202][MAX];
ll dp[2][MAX], P[MAX];

ll idx;
vector<double> idxs;
vector<int> pid;
vector<pii> S;

inline double Point(pii a, pii b) { 
	if (a.first == b.first) return 0;
	return (double)(b.second - a.second) / (double)(a.first - b.first); 
}

void Insert(pii line, int id) {
	while (S.size() > 1) {
		pii& pv = S[S.size() - 1], ppv = S[S.size() - 2];
		double cur = Point(ppv, pv), insert = Point(pv, line);
		if (cur <= insert) break;
		S.pop_back();
		idxs.pop_back();
		pid.pop_back();
	}
	if (!S.empty()) idxs.push_back(Point(S.back(), line));
	S.push_back(line);
	pid.push_back(id);
}

pii GetLinear(ll x) {
	while (idx < S.size() - 1 && Point(S[idx], S[idx + 1]) <= x) idx++;
	return { S[idx].first * x + S[idx].second, pid[idx] };
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, K;
	cin >> N >> K;
	for (int i = 1; i <= N; ++i) {
		cin >> P[i];
		P[i] += P[i - 1];
	}

	for (int k = 1; k <= K; ++k) {
		swap(dp[0], dp[1]);
		dp[0][0] = -2e9;
		idx = 0;
		idxs.clear();
		S.clear();
		pid.clear();

		Insert({ 0, 0 }, 0);
		for (int i = 1; i <= N; ++i) {
			pii q = GetLinear(P[i]);
			dp[1][i] = q.first;
			pv[k][i] = q.second;
			Insert({ P[i], dp[0][i] - P[i] * P[i] }, i);
		}
	}

	cout << dp[1][N] << '\n';
	vector<int> ans;
	int cur = N;
	for (int k = K; k > 0; --k) {
		ans.push_back(pv[k][cur]);
		cur = pv[k][cur];
	}
	for (int n : ans) cout << n << ' ';

	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, long long int> GetLinear(ll)':
sequence.cpp:35:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  while (idx < S.size() - 1 && Point(S[idx], S[idx + 1]) <= x) idx++;
      |         ~~~~^~~~~~~~~~~~~~

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