제출 #734172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
734172		SanguineChameleon	수열 (APIO14_sequence)	C++17	50 / 100	2076 ms	126376 KiB

sequence

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const long long inf = 1e18L + 20;
const int maxN = 1e5 + 20;
const int maxK = 2e2 + 20;
int a[maxN];
long long pref[maxN];
long long dp[maxN][maxK];
int best[maxN][maxK];

struct line {
	long long a = 0;
	long long b = 0;

	line() {};

	line(long long _a, long long _b): a(_a), b(_b) {};

	long long eval(long long x) {
		return a * x + b;
	};
};

long long floor_div(long long x, long long y) {
	return (x / y) - ((x ^ y) < 0 && x % y);
}

long long inter(line L1, line L2) {
	return floor_div(L2.b - L1.b, L1.a - L2.a);
}

struct CHT {
	vector<pair<int, line>> Q;

	void add(int id, line L) {
		while ((int)Q.size() >= 2) {
			if (Q.back().second.a == L.a) {
				if (Q.back().second.b >= L.b) {
					return;
				}
				else {
					Q.pop_back();
				}
			}
			else if (inter(Q.end()[-2].second, Q.back().second) >= inter(Q.back().second, L)) {
				Q.pop_back();
			}
			else {
				break;
			}
		}
		if (!Q.empty()) {
			if (Q.back().second.a == L.a) {
				if (Q.back().second.b >= L.b) {
					return;
				}
				else {
					Q.pop_back();
				}
			}
		}
		Q.emplace_back(id, L);
	}

	pair<int, long long> get(long long x) {
		long long mx = -inf;
		int best = -1;
		for (auto p: Q) {
			long long cur = p.second.eval(x);
			if (cur > mx) {
				mx = cur;
				best = p.first;
			}
		}
		return make_pair(best, mx);
	}
};

CHT C[maxK];

void just_do_it() {
	int N, K;
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
	}
	C[0].add(0, line(0, 0));
	for (int i = 1; i <= N; i++) {
		for (int j = min(i, K + 1); j >= 1; j--) {
			auto p = C[j - 1].get(pref[i]);
			best[i][j] = p.first;
			dp[i][j] = p.second + pref[i] * (pref[N] - pref[i]);
			C[j].add(i, line(pref[i], dp[i][j] - pref[i] * pref[N]));
		}
	}
	cout << dp[N][K + 1] << '\n';
	int cur = N;
	for (int i = K + 1; i >= 2; i--) {
		cout << (cur = best[cur][i]) << " ";
	}
}

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