제출 #261067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261067		atoiz	수열 (APIO14_sequence)	C++14	100 / 100	597 ms	82940 KiB

sequence

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

using pll = pair<int64_t, int64_t>;
#define x first
#define y second

const int64_t INF = 4e18;

int ccw(pll p0, pll p1, pll p2)
{
	double cross = (double) (p1.x - p0.x) * (p2.y - p0.y) - (double) (p2.x - p0.x) * (p1.y - p0.y);
	if (cross < -1e-5) return -1;
	if (cross > 1e-5) return 1;
	return 0;
}

int64_t calc(pll p, int64_t x) { return p.x * x + p.y; }

const int MAXN = 100007, MAXK = 207;
int trace[MAXK][MAXN];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N, K;
	cin >> N >> K;
	vector<int64_t> S(N + 1, 0);
	for (int i = 1; i <= N; ++i) cin >> S[i], S[i] += S[i - 1];
	vector<int64_t> ans(N + 1, INF);
	ans[0] = 0;

	vector<pll> vec;
	for (int t = 0; t <= K; ++t) {
		int ptr = 0;
		vec.clear();

		for (int i = 0; i <= N; ++i) {
			for (; ptr + 1 < (int) vec.size() && calc(vec[ptr], S[i]) > calc(vec[ptr + 1], S[i]); ++ptr);
			int64_t newAns = (ptr >= (int) vec.size() ? INF : calc(vec[ptr], S[i]) + S[i] * S[i]);
			if (ptr < ((int) vec.size())) trace[t][i] = vec[ptr].x / -2;
			if (ans[i] != INF) {
				pll cur(-2 * S[i], ans[i] + S[i] * S[i]);
				while (((int) vec.size()) > 1 && ccw(cur, vec.rbegin()[0], vec.rbegin()[1]) <= 0) vec.pop_back();
				vec.push_back(cur);
				ptr = min(ptr, ((int) vec.size()) - 1);
			}
			ans[i] = newAns;
		}
	}

	cout << (S[N] * S[N] - ans[N]) / 2 << endl;
	for (int t = K, i = N; t > 0; --t) {
		i = ((int) (upper_bound(S.begin(), S.begin() + i, trace[t][i]) - S.begin())) - 1;
		cout << i << ' ';
	}
	cout << endl;
}

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