제출 #1133356

#제출 시각아이디문제언어결과실행 시간메모리
1133356MuhammetGift (IZhO18_nicegift)C++17
100 / 100
263 ms73980 KiB
#include "bits/stdc++.h"

using namespace std;

#define SZ(s) (int)s.size()
#define ff first
#define ss second
#define ll long long

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int n, k;
	cin >> n >> k;
	ll sm = 0, mx = 0;
	vector <ll> a(n+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		sm += a[i];
		mx = max(a[i], mx);
	}
	if(sm % k != 0 or mx > (sm/k)){
		cout << -1;
		return 0;
	}
	queue <pair<ll,int>> q[k+1];
	int ind = 1, x = 1;
	ll s = 0, sk = sm/k;
	while(ind <= n){
		ll y = min(sk-s,a[ind]);
		q[x].push({y,ind});
		s += y;
		a[ind] -= y;
		if(a[ind] == 0) ind++;
		if(s == sk) x++, s = 0;
	}
	vector <ll> v;
	while(!q[1].empty()){
		ll mn = 1e18;
		for(int i = 1; i <= k; i++){
			mn = min(mn, q[i].front().ff);
		}
		v.push_back(mn);
		for(int i = 1; i <= k; i++){
			v.push_back(q[i].front().ss);
			q[i].front().ff -= mn;
			if(q[i].front().ff == 0) q[i].pop();
		}
	}
	cout << SZ(v)/(k+1) << '\n';
	int cnt = 0;
	for(auto i : v){
		cout << i << ' ';
		if(++cnt == k+1){
			cnt = 0;
			cout << '\n';
		}
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...