Submission #36739

#	Time	Username	Problem	Language	Result	Execution time	Memory
36739		junodeveloper	Split the sequence (APIO14_sequence)	C++14	60 / 100	2000 ms	86160 KiB

sequence

#include "bits/stdc++.h"
#define F first
#define S second
#define SZ(x) ((int)x.size())
using namespace std;
template<class T>
struct CHT {
	using pt = pair<T,T>;
	vector<pt> ln;
	vector<int> idx;
	int curr = 0;
	bool bad(pt& a, pt& b, T x) {
		return (b.S - a.S) >= x * (a.F - b.F);
	}
	bool bad(pt& a, pt& b, pt& c) {
		if(b.F == c.F) return b.S <= c.S;
		return (b.S - a.S) * (b.F - c.F) >= (c.S - b.S) * (a.F - b.F);
	}
	void insert(pt v, int i) {
		while(SZ(ln) >= 2 && bad(ln[SZ(ln)-2], ln.back(), v))
			ln.pop_back(), idx.pop_back();
		ln.push_back(v), idx.push_back(i);
	}
	pair<T, int> query(T x) {
		assert(SZ(ln) > 0);
		curr = min(curr, SZ(ln) - 1);
		while(curr < SZ(ln) - 1 && bad(ln[curr], ln[curr+1], x))
			curr++;
		return {x * ln[curr].F + ln[curr].S, idx[curr]};
	}
	void clear() {
		ln.clear();
		idx.clear();
		curr = 0;
	}
};
int n, k, rec[100010][202];
long long s[100010], dp[100010], currDP;
CHT<long long> cht;
int main() {
	scanf("%d%d", &n, &k);
	for(int i=1; i<=n; i++) scanf("%lld", s+i), s[i] += s[i-1];
	for(int j=2; j<=k+1; j++) {
		cht.clear();
		cht.insert({s[j-1], dp[j-1] - s[j-1]*s[j-1]}, j-1);
		for(int i=j; i<=n; i++) {
			tie(currDP, rec[i][j]) = cht.query(s[i]);
			cht.insert({s[i], dp[i] - s[i]*s[i]}, i);
			dp[i] = currDP;
		}
	}
	printf("%lld\n", dp[n]);
	int p = n;
	vector<int> res;
	while(k > 0) {
		res.push_back(rec[p][k+1]);
		p = rec[p][k+1], k--;
	}
	for(int i=SZ(res)-1; i>=0; i--) printf("%d ", res[i]);
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:41:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
sequence.cpp:42:60: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%lld", s+i), s[i] += s[i-1];
                                                            ^

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