글 읽기 - 데이터 추가 부탁드립니다

(追記) (追記ここまで)

데이터 추가 부탁드립니다

2613번 - 숫자구슬

jyheo98 5년 전 1

입력

6 4

1 1 1 4 1 1

출력

2 1 2 1 되었는데도 맞다고 채점되었어요.

정답은

1 2 1 2 혹은

2 1 1 2입니다

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
using llong = long long;
int n, m;
vector<int> a;
int check(int k)
{
	int i;
	int cnt = 0, sum = 0;
	for (i = 0; i < n; i++) if (a[i] > k) return false;
	for (i = 0; i < n; i++)
	{
		sum += a[i];
		if (sum == k)
		{
			sum = 0;
			cnt++;
		}
		else if (sum > k)
		{
			sum = a[i];
			cnt++;
		}
	}
	if (sum != 0) cnt++;
	return cnt;
}
int main()
{
	IOS;
	cin >> n >> m;
	a.resize(n);
	int i;
	int maxx = 0;
	
	for (i = 0; i < n; i++)
	{
		cin >> a[i];
		if (maxx < a[i])maxx = a[i];
	}
	int ll = maxx, rr = 30000;
	while (ll < rr)
	{
		int mid = (ll + rr) / 2;
		if (check(mid) > m) ll = mid + 1;
		else rr = mid;
	}
	cout << ll << "\n";
	int sum = 0, cnt = 0;
	vector<int> ans;
	for (i = 0; i < n; i++)
	{
		cnt++;
		sum += a[i];
		if (sum > ll)
		{
			ans.push_back(cnt - 1);
			cnt = 1;
			sum = a[i];
		}
		else if (sum == ll)
		{
			ans.push_back(cnt);
			cnt = 0;
			sum = 0;
		}
	}
	if(sum !=0)
		ans.push_back(cnt);
	int chai = m - ans.size();
	for (i = 1; i <= chai ; i++)
	{
		for (int j = 0; j < ans.size(); j++)
		{
			if (ans[j] > 1)
			{
				ans[j] --;
				ans.push_back(1);
				break;
			}
		}
	}
	for (i = 0; i < ans.size(); i++) cout << ans[i] << " ";
	return 0;
}