Submission #369389

#	Time	Username	Problem	Language	Result	Execution time	Memory
369389		GioChkhaidze	Split the sequence (APIO14_sequence)	C++14	89 / 100	924 ms	84860 KiB

sequence

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second

using namespace std;

const int N = 1e5 + 5;

ll n, k, a[N], S[N], dp[N];
int P[N][202];

struct Line {
	ll k, b, id;

	ll vl(ll x) {
		return k * x + b;
	}
	
	pair <ll , ll > intr(const Line& yo) {
		ll one = yo.b - b;
		ll two = k - yo.k;
		if (two < 0) one *= -1, two *= -1;
		return {one, two};
	}
};

deque < Line > dq;
void insert(ll k, ll b, ll id) {
	Line line = {k, b, id};
	while (dq.size() > 1) {
		Line linea = dq.end()[-1];
		Line lineb = dq.end()[-2];
		pair < ll , ll > A = lineb.intr(linea);
		pair < ll , ll > B = linea.intr(line);
		if (A.F * B.S >= B.F * A.S) dq.pop_back();
			else break;
	}
	
	dq.push_back(line);
}

pair < ll , int > qr(int x, int idx) {
	while (dq.size() > 1 && dq[0].id < idx) {
		if (dq[0].vl(x) <= dq[1].vl(x)) dq.pop_front();
			else break;
	}
	return {dq[0].vl(x), dq[0].id};
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		S[i] = S[i - 1] + a[i];
	}
	
	Line bs = {0, 0, 0};
	dq.push_front(bs);
	for (int st = 1; st <= k; ++st) {
		for (int i = st; i <= n; ++i) {
			pair < ll , int > lol = qr(S[i], i);
			P[i][st] = lol.S;
			dp[i] = lol.F + (S[n] - S[i]) * S[i];
		}
		
		while (dq.size()) dq.pop_back();
		dq.push_front(bs);
		for (int j = st; j <= n; ++j) {
			insert(S[j], dp[j] - S[n] * S[j], j);
		}
	}
	
	vector < int > ans;
	ll idx = k, res = dp[k];
	for (int i = k + 1; i <= n; ++i) {
		if (dp[i] > res) {
			res = dp[i];
			idx = i;
		}
	}
	
	cout << res << "\n";
	for (int i = k; i >= 1; --i) {
		ans.push_back(idx);
		idx = P[idx][i];
	}
	
	reverse(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); ++i) {
		cout << ans[i] << " ";
	}
}

Compilation message (stderr)

sequence.cpp:52:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main () {
      |       ^
sequence.cpp: In function 'int main()':
sequence.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for (int i = 0; i < ans.size(); ++i) {
      |                  ~~^~~~~~~~~~~~

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