제출 #1214171

#제출 시각아이디문제언어결과실행 시간메모리
1214171PenguinsAreCuteCookies (JOI23_cookies)C++17
7 / 100
3 ms1156 KiB
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, tot = 0;
	cin >> n;
	priority_queue<pair<int,int>> pq;
	for(int i=0,a;i<n;i++) {
		cin >> a;
		tot += a;
		pq.push({a,i});
	}
	vector<vector<int>> sol;
	auto add = [&pq,&sol](int s) {
		sol.push_back(vector<int>(s,0));
		vector<pair<int,int>> used;
		for(int i=0;i<s;i++) {
			auto [cnt, idx] = pq.top();
			assert(cnt);
			pq.pop();
			used.push_back({cnt-1,idx});
			sol.back()[i] = idx;
		}
		for(auto i: used)
			pq.push(i);
	};
	int m;
	cin >> m;
	int b[m];
	for(int i=0;i<m;i++)
		cin >> b[i];
	int dp[m][b[0]];
	memset(dp,1,sizeof(dp));
	dp[0][0] = 0;
	for(int i=1;i<m;i++) {
		memcpy(dp[i],dp[i-1],sizeof(dp[i]));
		for(int j=0;j<b[0];j++)
			dp[i+1][(j+b[i])%b[0]] = min(dp[i+1][(j+b[i])%b[0]],dp[i+1][j]+b[i]-b[0]);
		for(int j=0;j<b[0];j++)
			dp[i+1][(j+b[i])%b[0]] = min(dp[i+1][(j+b[i])%b[0]],dp[i+1][j]+b[i]-b[0]);
	}
	if(dp[m-1][tot%b[0]] > tot - 1LL * b[0] * pq.top().first) {
		cout << -1;
		return 0;
	}
	int i0 = m-1, j0 = tot % b[0];
	while(i0) {
		if(dp[i0][j0] == dp[i0][((j0-b[i0])%b[0]+b[0])%b[0]] + b[i0] - b[0]) {
			add(b[i0]);
			j0 = ((j0 - b[i0]) % b[0] + b[0]) % b[0];
			tot -= b[i0];
		} else
			i0--;
	}
	for(int i=0;i<tot/b[0];i++)
		add(b[0]);
	cout << sol.size() << "\n";
	for(auto i: sol) {
		cout << i.size() << " ";
		for(auto j: i)
			cout << j+1 << " ";
		cout << "\n";
	}
}
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...