Submission #101665

#	Time	Username	Problem	Language	Result	Execution time	Memory
101665		arman_ferdous	Split the sequence (APIO14_sequence)	C++14	71 / 100	267 ms	132096 KiB

sequence

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

using ll = long long;
const int N = 100010;
const int K = 210;
const ll oo = 1e18;

int n, k;
ll a[N], S[N], dp[N][K], opt[N][K];

struct CHT{
	vector<ll> m, c; vector<int> id;
	void init() { m.clear(); c.clear(); id.clear(); }
	bool bad(int i, int j, int k) {
		return 1.0 * (c[j] - c[i]) * (m[i] - m[k]) >= 1.0 * (c[k] - c[i]) * (m[i] - m[j]);
	}
	void insert(ll M, ll C, int id_) {
		m.push_back(M); c.push_back(C); id.push_back(id_);
		int sz = m.size();
		while(sz >= 3 && bad(sz-3, sz-2, sz-1)) {
			m.erase(m.end()-2);
			c.erase(c.end()-2);
			id.erase(id.end()-2);
			sz--;
		}
	}
	ll f(int i, ll X) { return m[i] * X + c[i]; }
	pair<ll,int> get(ll X) {
		int lo = 0, hi = m.size()-1;
		if(hi < lo) return {-oo, -1};
		while(hi - lo >= 5) {
			int mid1 = (lo + lo + hi) / 3;
			int mid2 = (lo + hi + hi) / 3;
			if(f(mid1,X) >= f(mid2,X)) hi = mid2 - 1;
			else lo = mid1 + 1;
		} ll ret = -oo; int id_ = 0;
		for(int i = lo; i <= hi; i++) {
			if(f(i,X) > ret)
				id_ = id[i], ret = f(i,X);
		}
		return {ret,id_};
	}
}ds;

int soln[K], ptr;
int main() {
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		S[i] = S[i-1] + a[i];
	}

	for(int kk = 1; kk <= k; kk++) {
		ds.init();
		for(int i = 1; i <= n; i++) {
			auto got = ds.get(S[i]);
			dp[i][kk] = got.first;
			opt[i][kk] = got.second;
			ds.insert(S[i], dp[i][kk-1] - S[i]*S[i], i);
		}
	}
	printf("%lld\n", dp[n][k]);
	int pos = n;
	for(int cnt = k; cnt > 0; cnt--) {
		printf("%lld ", opt[pos][cnt]);
		if(pos > 0) pos = opt[pos][cnt];
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
   ~~~~~^~~~~~~~~~~~~~~

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