Submission #101681

#	Time	Username	Problem	Language	Result	Execution time	Memory
101681		arman_ferdous	Split the sequence (APIO14_sequence)	C++17	100 / 100	491 ms	82888 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
const int N = 100005;
const int K = 205;
const ll oo = 1e18;
 
int n, k;
ll S[N], dp[2][N]; int opt[K][N];
 
struct CHT{
	ll m[N], c[N]; int id[N], sz, last;
	void init() { sz = last = 0; }
	bool bad(int i, int j, int k) {
		return (c[j] - c[i]) * (m[i] - m[k]) >= (c[k] - c[i]) * (m[i] - m[j]);
	}
	void insert(ll M, ll C, int id_) {
		m[sz] = M, c[sz] = C, id[sz] = id_; sz++;
		while(sz >= 3 && bad(sz-3, sz-2, sz-1)) {
			m[sz-2] = m[sz-1];
			c[sz-2] = c[sz-1];
			id[sz-2] = id[sz-1];
			sz--;
		}
	}
	ll f(int i, ll X) { return m[i] * X + c[i]; }
	pair<ll,int> get(ll X) {
		last = min(last, sz-1);
		while(last + 1 < sz && f(last,X) <= f(last+1,X))
			last++;
		return {f(last,X), id[last]};
	}
}ds;
 
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 kk = 1; kk <= k; kk++) {
		int row = (kk&1);
		ds.init();
		ds.insert(0,0,0);
		for(int i = kk; i <= n; i++) {
			auto got = ds.get(S[i]);
			dp[row][i] = got.first;
			opt[kk][i] = got.second;
			ds.insert(S[i], dp[(row^1)][i] - S[i]*S[i], i);
		}
	}
	printf("%lld\n", dp[(k&1)][n]);
	while(n && k) {
		printf("%d ", opt[k][n]);
		n = opt[k][n];
		k--;
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:37: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:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &S[i]);
   ~~~~~^~~~~~~~~~~~~~~

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