Submission #991778

#	Time	Username	Problem	Language	Result	Execution time	Memory
991778		xnqs	Split the sequence (APIO14_sequence)	C++14	100 / 100	1379 ms	83396 KiB

sequence

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

const int BLN = 5;
int x, k;
int arr[100005];
int pfx[100005];
int64_t dp[100005][2];
int last[100005][205];

inline int sum_query(int l, int r) {
	return pfx[r] - pfx[l-1];
}

void dnc(int lvl, int l, int r, int optl, int optr) {
	if (l>r) {
		return;
	}

	int m = (l+r)>>1;
	std::pair<int64_t,int> opt(-0x3f3f3f3f3f3f3f3f,-0x3f3f3f3f);
	for (int i = std::max(0, optl-BLN); i < std::min(m, optr+1+BLN); i++) {
		opt = std::max(opt,std::pair<int64_t,int>(1LL*sum_query(i+1,m)*sum_query(m+1,x)+dp[i][(lvl-1)&1], i));
	}

	dp[m][lvl&1] = opt.first;
	last[m][lvl] = opt.second;
	dnc(lvl,l,m-1,optl,opt.second);
	dnc(lvl,m+1,r,opt.second,optr);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> k;
	for (int i = 1; i <= x; i++) {
		std::cin >> arr[i];
		pfx[i] = pfx[i-1] + arr[i];
	}

	++k;
	for (int i = 1; i <= k; i++) {
		dnc(i,1,x,1,x);
	}

	std::cout << dp[x][k&1] << "\n";

	int i = x, j = k;
	std::vector<int> stk;
	while (j) {
		if (i!=x) stk.emplace_back(i);
		i = last[i][j];
		--j;
	}

	int last = 0;
	while (!stk.empty()) {
		std::cout << stk.back() << " ";
		stk.pop_back();
	}
	std::cout << "\n";
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:65:6: warning: unused variable 'last' [-Wunused-variable]
   65 |  int last = 0;
      |      ^~~~

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