Submission #112347

#	Time	Username	Problem	Language	Result	Execution time	Memory
112347		ainta	Split the sequence (APIO14_sequence)	C++17	50 / 100	170 ms	6784 KiB

sequence

#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 101000
using namespace std;
int n, K, w[N_], MnC[N_], MxC[N_], MxP[N_], MnP[N_];
long long S[N_], D[N_];
struct Seg {
	long long A, B;
	int num;
}Deq[N_];
bool Over(Seg a, Seg b, Seg c) {
	return (b.B - a.B)*(a.A - c.A) >= (c.B - a.B)*(a.A - b.A);
}
long long Get(Seg a, long long x) {
	return a.A*x + a.B;
}
void Calc(long long M) {
	int i;
	int head = 1, tail = 0;
	Deq[++tail] = { 0,0,0 };
	for (i = 1; i <= n; i++) {
		while (head < tail && Get(Deq[head], S[i]) >= Get(Deq[head + 1], S[i]))head++;
		MxC[i] = MxC[Deq[head].num] + 1;
		MxP[i] = Deq[head].num;
		D[i] = Get(Deq[head], S[i]) + S[i] * S[i] + M;
		Seg tp = { -2 * S[i],D[i] + S[i] * S[i],i };
		while (head < tail && Over(Deq[tail - 1], Deq[tail], tp))tail--;
		Deq[++tail] = tp;
	}
	head = 1, tail = 0;
	Deq[++tail] = { 0,0,0 };
	for (i = 1; i <= n; i++) {
		while (head < tail && Get(Deq[head], S[i]) > Get(Deq[head + 1], S[i]))head++;
		MnC[i] = MnC[Deq[head].num] + 1;
		MnP[i] = Deq[head].num;
		D[i] = Get(Deq[head], S[i]) + S[i] * S[i] + M;
		Seg tp = { -2 * S[i],D[i] + S[i] * S[i],i };
		while (head < tail && Over(Deq[tail - 1], Deq[tail], tp))tail--;
		Deq[++tail] = tp;
	}
}
int main() {
	int i;
	scanf("%d%d", &n, &K);
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		S[i] = S[i - 1] + w[i];
	}
	K++;
	long long b = 0, e = 4e18, mid, r = 0;
	while (b <= e) {
		mid = (b + e) >> 1;
		Calc(mid);
		if (MxC[n] >= K) {
			r = mid;
			b = mid + 1;
		}
		else e = mid - 1;
	}
	Calc(r);
	int ed = n, c = 0;
	long long s = 0;
	vector<int>Res;
	for (i = n - 1; i >= 0; i--) {
		if (MnC[i] + c + 1 <= K && MxC[i] + c + 1 >= K && s + (S[ed] - S[i])*(S[ed] - S[i]) + r + D[i] == D[n]) {
			if (i)Res.push_back(i);
			c++, s += (S[ed] - S[i])*(S[ed] - S[i]) + r;
			ed = i;
		}
	}
	reverse(Res.begin(), Res.end());
	long long Ans = (S[n] * S[n] - D[n] + r * K)/2;
	printf("%lld\n", Ans);
	for (auto &t : Res)printf("%d ", t);
}

Compilation message (stderr)

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

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