Submission #540463

#	Time	Username	Problem	Language	Result	Execution time	Memory
540463		dutinmeow	Split the sequence (APIO14_sequence)	C++17	0 / 100	36 ms	9612 KiB

sequence

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

#pragma region debug
#ifndef NDEBUG
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	return os << '(' << p.first << ", " << p.second << ')';
}

template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}

template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
	return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	os << '[';
	if (v.size()) {
		os << *v.begin();
		for (auto i = ++v.begin(); i != v.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &v) {
	os << '[';
	if (N) {
		os << *v.begin();
		for (auto i = ++v.begin(); i != v.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = ++s.begin(); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = ++s.begin(); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
	os << '[';
	if (s.size()) {
		os << *s.begin();
		for (auto i = ++s.begin(); i != s.end(); i++)
			os << ", " << (*i);
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &s) {
	os << '[';
	if (s.size()) {
		os << '(' << s.begin()->FF << " : " << s.begin()->SS << ')';
		for (auto i = ++s.begin(); i != s.end(); i++)
			os << ", " << '(' << i->FF << " : " << i->SS << ')';
	}
	return os << ']';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const unordered_map<T1, T2>& s) {
	os << '[';
	if (s.size()) {
		os << '(' << s.begin()->FF << " : " << s.begin()->SS << ')';
		for (auto i = ++s.begin(); i != s.end(); i++)
			os << ", " << '(' << i->FF << " : " << i->SS << ')';
	}
	return os << ']';
}

#define dbg1(a) cerr << #a << " = " << a << '\n';
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg8, dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define dbg(...) 
#endif
#pragma endregion debug

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<int> A(N + 1), P(N + 1, 0);
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		P[i] = P[i - 1] + A[i];
	}

	vector<vector<long long>> dp(K + 2, vector<long long>(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[k - 1][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[k][i] = dq[0].first(P[i]) + P[i] * P[N] - P[i] * P[i];
			par[k][i] = dq[0].second;
		}
	}

	cout << dp[K + 1][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';

	/*
	cerr << "dp:\n";
	for (int k = 1; k <= K + 1; k++) {
		dbg(dp[k]);
	}

	cerr << "par:\n";
	for (int k = 1; k <= K + 1; k++) {
		dbg(par[k]);
	}*/
}

Compilation message (stderr)

sequence.cpp:4: warning: ignoring '#pragma region debug' [-Wunknown-pragmas]
    4 | #pragma region debug
      | 
sequence.cpp:111: warning: ignoring '#pragma endregion debug' [-Wunknown-pragmas]
  111 | #pragma endregion debug
      |

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