Submission #540468

#	Time	Username	Problem	Language	Result	Execution time	Memory
540468		dutinmeow	Split the sequence (APIO14_sequence)	C++17	100 / 100	848 ms	84440 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

struct Line {
    long long m, b;

    Line(long long _m, long long _b) : m(_m), b(_b) {}

    long long operator()(long long x) { return m * x + b; }

    friend long double intersect(const Line &l1, const Line &l2) { 
		return (long double)(l2.b - l1.b) / (long double)(l1.m - l2.m); 
	}

    friend ostream& operator<<(ostream &os, const Line &l) { 
		return os << '{' << l.m << "x + " << l.b << '}'; 
	}
};

int main() {
	int N, K;
	cin >> N >> K;
	vector<long long> A(N + 1), P(N + 1, 0);
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		P[i] = P[i - 1] + A[i];
	}

	array<vector<long long>, 2> dp;
	dp[0].assign(N + 1, 0), dp[1].assign(N + 1, 0);
	vector<vector<int>> par(K + 2, vector<int>(N + 1, 0));
	for (int k = 1; k <= K + 1; k++) {
		deque<pair<Line, int>> dq;
		for (int i = 1; i <= N; i++) {
			Line l(P[i - 1], dp[0][i - 1] - P[i - 1] * P[N]);
			while (dq.size() >= 2 && intersect(l, dq[dq.size() - 2].first) >= intersect(l, dq[dq.size() - 1].first)) 
				dq.pop_back();
			dq.emplace_back(move(l), i - 1);
			
			while (dq.size() >= 2 && dq[0].first(P[i]) <= dq[1].first(P[i]))
				dq.pop_front();	
			dp[1][i] = dq[0].first(P[i]) + P[i] * P[N] - P[i] * P[i];
			par[k][i] = dq[0].second;
		}
		copy(dp[1].begin(), dp[1].end(), dp[0].begin());
	}

	cout << dp[0][N] << '\n';
	vector<int> ans;
	for (int k = K + 1, c = N; k > 0; k--) {
		if (c != N)
			ans.push_back(c);
		c = par[k][c];
	}
	reverse(ans.begin(), ans.end());
	for (int c : ans)
		cout << c << ' ';
	cout << '\n';
}

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