Submission #48052

#	Time	Username	Problem	Language	Result	Execution time	Memory
48052		E869120	수열 (APIO14_sequence)	C++14	0 / 100	74 ms	67804 KiB

sequence

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct State { long long L, R, px, py; };

bool operator<(const State &a1, const State &a2) {
	if (a1.L < a2.L) return true;
	return false;
}

class ConvexHullTrick {
public:
	vector<State>S;

	long long merge(long long vx, long long vy, long long wx, long long wy) {
		long long F = wy + (wx - vx)*(wx - vx) - vy;
		long long G = F / (2LL * (wx - vx));
		return G;
	}

	void add(long long vx, long long vy) {
		long long LL = -(1LL << 60);
		while (!S.empty()) {
			State G = S[S.size() - 1];
			if (G.px == vx) {
				if (G.py > vy) {
					S.pop_back();
				}
				else {
					return;
				}
			}
			else {
				long long D = merge(G.px, G.py, vx, vy);
				if (G.L > D) {
					S.pop_back();
				}
				else {
					S[S.size() - 1].R = D;
					S.push_back(State{ D + 1,(1LL << 60),vx,vy });
					return;
				}
			}
		}
		S.push_back(State{ LL, (1LL << 60),vx,vy });
	}
	pair<long long, long long> mincost(long long pos) {
		int pos1 = lower_bound(S.begin(), S.end(), State{ pos, (1LL << 60), 0LL, 0LL }) - S.begin(); pos1--;
		State G = S[pos1];
		return make_pair(G.py + (pos - G.px)*(pos - G.px), G.px);
	}
};

long long N, K, A[100009], S; pair<long long, long long>dp[10009][209];

int main() {
	cin >> N >> K; K++;
	for (int i = 1; i <= N; i++) { cin >> A[i]; S += A[i]; }
	for (int i = 1; i <= N; i++) A[i] += A[i - 1];

	for (int i = 0; i <= N; i++) { for (int j = 0; j <= K; j++) dp[i][j] = make_pair((1LL << 60), -1); }

	dp[0][0] = make_pair(0, -1);
	for (int j = 1; j <= K; j++) {
		ConvexHullTrick X;
		for (int i = 1; i <= N; i++) {
			X.add(A[i - 1], dp[i - 1][j - 1].first);

			pair<long long, long long>T = X.mincost(A[i]);
			dp[i][j].first = T.first;
			int pos1 = lower_bound(A, A + N + 1, T.second) - A;
			dp[i][j].second = pos1;
		}
	}
	vector<int>C; int cx = N, cy = K;
	while (cx >= 1) {
		if (cx != N) C.push_back(cx);
		cx = dp[cx][cy].second; cy--;
	}
	reverse(C.begin(), C.end());
	cout << (S*S - dp[N][K].first) / 2 << endl;
	for (int i = 0; i < C.size(); i++) {
		if (i)cout << " "; cout << C[i];
	}
	cout << endl;
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < C.size(); i++) {
                  ~~^~~~~~~~~~
sequence.cpp:85:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (i)cout << " "; cout << C[i];
   ^~
sequence.cpp:85:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if (i)cout << " "; cout << C[i];
                      ^~~~

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