Submission #218398

#	Time	Username	Problem	Language	Result	Execution time	Memory
218398		spdskatr	Split the sequence (APIO14_sequence)	C++14	0 / 100	260 ms	7032 KiB

sequence

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef pair<long double, int> line;
typedef __int128_t ll;

int N, K, ar[100005], ps[100005];
int cnt[100005], from[100005];
ll dp[100005], m[100005], c[100005];
vector<int> cht;

void ins(int j) {
	m[j] = ps[j];
	c[j] = dp[j] - ps[j]*ps[N];
	while (cht.size() > 1) {
		int s = cht[cht.size() - 2];
		int t = cht[cht.size() - 1];
		if ((c[s] - c[j])*(m[t] - m[s]) <= (c[s] - c[t])*(m[j] - m[s])) {
			cht.pop_back();
		} else break;
	}
	cht.push_back(j);
}


void solve(ll x) {
	memset(dp, 0, sizeof(dp));
	memset(m, 0, sizeof(m));
	memset(c, 0, sizeof(c));
	memset(cnt, 0, sizeof(cnt));
	memset(from, 0, sizeof(from));
	cht.clear();
	int ptr = 0;
	cht.push_back(0);
	for (int i = 1; i <= N; i++) {
		dp[i] = m[cht[ptr]] * ps[i] + c[cht[ptr]];
		cnt[i] = cnt[cht[ptr]] + 1;
		from[i] = cht[ptr];
		while (ptr + 1 < cht.size()) {
			ll nv = m[cht[ptr+1]] * ps[i] + c[cht[ptr+1]];
			if (nv <= dp[i]) break;
			dp[i] = nv;
			cnt[i] = cnt[cht[ptr+1]] + 1;
			from[i] = cht[ptr+1];
			ptr++;
		}
		dp[i] += ps[i] * (ps[N] - ps[i]) - x;
		ins(i);
	}
}

int main() {
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; i++) {
		scanf("%d", ar+i);
		ps[i] = ps[i-1] + ar[i];
	}
	ll lo = -1, hi = 1e18;
	while (lo + 1 < hi) {
		ll mid = (lo + hi) / 2;
		solve(mid);
		if (cnt[N] > K + 1) lo = mid;
		else hi = mid;
	}
	// Minimised maximum is hi
	//printf("Penalty: %lld\n", (long long)hi);
	solve(hi);
	//printf("Splits: %d\n", cnt[N]);
	ll ans = dp[N] + hi * (K+1);
	printf("%lld\n", (long long)ans);
	int cur = N;
	vector<int> pos;
	while (cur != 0) {
		cur = from[cur];
		if (cur != 0) pos.push_back(cur);
	}
	for (int i = (int)pos.size() - 1; i >= 0; i--) {
		if (i == 0) printf("%d\n", pos[i]);
		else printf("%d ", pos[i]);
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void solve(ll)':
sequence.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ptr + 1 < cht.size()) {
          ~~~~~~~~^~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:60: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:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", ar+i);
   ~~~~~^~~~~~~~~~~~

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