Submission #1133527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133527		stdfloat	Gift (IZhO18_nicegift)	C++20	100 / 100	361 ms	104840 KiB

nicegift

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

using ll = long long;

#define sz(v)	(int)(v).size()
#define all(v)	(v).begin(), (v).end()

#define ff	first
#define ss	second
#define pli	pair<ll, int>

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

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

	vector<ll> a(n);
	for (auto &i : a)
		cin >> i;

	ll sm = accumulate(all(a), 0LL);

	if (sm % k || *max_element(all(a)) > sm / k) return cout << -1, 0;

	vector<ll> u = {0};
	vector<deque<pli>> v = {{}};
	for (int i = 0; i < n; i++) {
		if (a[i] <= sm / k - u.back()) {
			u.back() += a[i];
			v.back().push_back({a[i], i});
		}
		else {
			if (sm / k != u.back()) v.back().push_back({sm / k - u.back(), i});
			v.push_back({{a[i] - sm / k + u.back(), i}});
			u.push_back(a[i] - sm / k + u.back());
		}
	}

	vector<vector<ll>> ans;
	while (!v[0].empty()) {
		ll mn = LLONG_MAX;
		for (int i = 0; i < k; i++)
			mn = min(mn, v[i].front().ff);
	
		ans.push_back({mn});
		for (int i = 0; i < k; i++) {
			ans.back().push_back(v[i].front().ss + 1);
			v[i].front().ff -= mn;
			if (!v[i].front().ff) v[i].pop_front();
		}
	}

	cout << sz(ans) << '\n';
	for (auto i : ans) {
		for (auto j : i)
			cout << j << ' ';
		cout << '\n';
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 51 / 51