Submission #399576

#	Time	Username	Problem	Language	Result	Execution time	Memory
399576		Azimjon	Split the sequence (APIO14_sequence)	C++17	0 / 100	108 ms	8628 KiB

sequence

// Muallif: Azimjon Mehmonali o'g'li

#include <bits/stdc++.h>

using namespace std;

#define int long long

const long double PI = 3.1415926535897;
const int mod = 1000000007LL;
const int INF = 1e18;
const int N = 111111;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;

	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}

	vector<vector<pair<int, int>>> g;
	g.push_back(a);

	int jv = 0;
	vector<int> el;

	while (k--) {
		int ka, ki;
		ka = -INF;
		ki = -1;

		for (auto v : g) {
			int yi = 0;
			for (auto [x, y] : v)
				yi += x;
			int hy = 0;
			for (int i = 0; i < (int)v.size(); i++) {
				hy += v[i].first;

				if (hy * (yi - hy) > ka) {
					ka = hy * (yi - hy);
					ki = v[i].second;
				}
			}
		}

		jv += ka;
		el.push_back(ki);
		int oc;
		vector<pair<int, int>> qq, ww;
		for (int j = 0; j < (int)g.size(); j++) {
			auto v = g[j];
			int ii = -1;
			for (int i = 0; i < (int)v.size(); i++) {
				if (ki == v[i].second) {
					ii = i;
				}
			}

			if (ii != -1) {
				vector<pair<int, int>> tr;

				for (int i = 0; i <= ii; i++) {
					qq.push_back(v[i]);
				}

				g.push_back(tr);

				for (int i = ii + 1; i < (int)v.size(); i++) {
					ww.push_back(v[i]);
				}

				oc = j;
				break;
			}
		}
		g.push_back(qq);
		g.push_back(ww);

		g.erase(g.begin() + oc);
	}

	cout << jv << endl;

	for (int i : el) {
		cout << i + 1 << " ";
	}

	return 0;
}

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