Submission #59196

#	Time	Username	Problem	Language	Result	Execution time	Memory
59196		IOrtroiii	Split the sequence (APIO14_sequence)	C++11	71 / 100	2077 ms	132096 KiB

sequence

/*input
7 3
4 1 3 4 0 2 3
*/
#include <bits/stdc++.h>
using namespace std;

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

struct Line {
	long long a, b;
	Line(long long a = 0, long long b = 0) : a(a),  b(b) {}
	void print() {
		cout << a << "x + " << b << '\n';
	}
};

bool bad(Line l1,Line l2,Line l3) {
	return (l1.b - l3.b) * (l2.a - l1.a) <= (l3.a - l1.a) * (l1.b - l2.b);
}

struct ConvexHullTrick {
	#define l1 L[L.size() - 2]
	#define l2 L[L.size() - 1]
	vector<Line> L;
	ConvexHullTrick() { L.clear(); }
	
	void add(Line l3) {
		while (L.size() >= 2 && bad(l1, l2, l3)) L.pop_back();
		L.push_back(l3);
	}
	
	long long calc(int pos,long long x) {
		if (pos == L.size()) return (long long) -4e18;
		return L[pos].a * x + L[pos].b;
	}
	
	long long get(long long x) {
		int l = 0, r = L.size() - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (calc(mid, x) >= calc(mid + 1, x)) r = mid;
			else l = mid + 1;
		}
		return calc(l, x);
	}
	void print() {
		for (auto line : L) line.print();
	}
	#undef l1
	#undef l2
} cht[205];

const int N = 1e5 + 5;

int n, k;
long long a[N], prf[N];
long long f[205][N];

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		prf[i] = prf[i - 1] + a[i];
	} 
	for (int i = 1; i <= n; ++i) f[0][i] = 0;
	for (int i = 1; i <= k; ++i) {
		cht[i - 1] = ConvexHullTrick();
		cht[i - 1].add(Line());
		for (int j = 1; j <= n; ++j) {
			f[i][j] = cht[i - 1].get(prf[j]);
			cht[i - 1].add(Line(prf[j], f[i - 1][j] - prf[j] * prf[j]));
		}
	}
	cout << f[k][n] << '\n';
	vector<int> trc;
	int prv = n, ptr = n - 1;
	while (k) {
		if (f[k - 1][ptr] + prf[ptr] * (prf[prv] - prf[ptr]) == f[k][prv]) {
			prv = ptr, k--;
			trc.push_back(ptr);
		}
		ptr--;
	}
	reverse(trc.begin(), trc.end());
	for (int pos : trc) cout << pos << ' ';
	
}

Compilation message (stderr)

sequence.cpp: In member function 'long long int ConvexHullTrick::calc(int, long long int)':
sequence.cpp:35:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (pos == L.size()) return (long long) -4e18;
       ~~~~^~~~~~~~~~~
sequence.cpp: In member function 'long long int ConvexHullTrick::get(long long int)':
sequence.cpp:42:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = 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: 0 / 29