Submission #790655

#	Time	Username	Problem	Language	Result	Execution time	Memory
790655		qwerasdfzxcl	Cookies (JOI23_cookies)	C++17	100 / 100	232 ms	350284 KiB

cookies

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<bitset<15015>> dp[15015];
bitset<15015> B[15015];
int a[15015], b[15015], valid[15015], n;

void output(int x, int y, int z){
	vector<int> V;

	while(x > 0){
		// printf("%d %d %d\n", x, y, z);
		if (y+1 < (int)dp[x].size() && dp[x][y+1][z]) y++;
		else{
			assert(y < (int)dp[x-1].size());
			assert(dp[x-1][y][z-b[y]]);

			V.push_back(b[y]);
			z -= b[y];
			x--;
		}
	}

	assert(z==0);

	priority_queue<pair<int, int>> pq;
	for (int i=1;i<=n;i++) pq.emplace(a[i], i);
	vector<vector<int>> ans;

	for (auto &x:V){
		assert((int)pq.size() >= x);
		ans.emplace_back();
		vector<pair<int, int>> buf;

		for (int i=1;i<=x;i++){
			ans.back().push_back(pq.top().second);
			if (pq.top().first > 1) buf.emplace_back(pq.top().first-1, pq.top().second);
			pq.pop();
		}

		for (auto &p:buf) pq.push(p);
	}

	printf("%d\n", (int)ans.size());
	for (auto &V:ans){
		printf("%d ", (int)V.size());
		for (auto &x:V) printf("%d ", x);
		printf("\n");
	}

	exit(0);
}

int main(){
	int S = 0;
	scanf("%d", &n);

	for (int i=1;i<=n;i++){
		scanf("%d", a+i);
		S += a[i];
	}

	int m;
	scanf("%d", &m);

	for (int i=1;i<=m;i++) scanf("%d", b+i);

	for (int i=1;i<=n;i++){
		for (int j=1;j<=a[i];j++) valid[j]++;		
	}

	B[0].set(0);
	for (int i=1;i<=S;i++){
		valid[i] += valid[i-1];
		
		for (int j=1;j<=valid[i]-valid[i-1];j++) B[i].set(j+valid[i-1]);
		B[i] |= B[i-1];
	} 
	for (int i=1;i<=S;i++) dp[i].resize(min(S/i, m) + 1);
	dp[0].resize(min(S, m) + 1);
	for (int j=1;j<=m;j++) dp[0][j].set(0);

	for (int i=1;i<=S;i++){
		for (int j=(int)dp[i].size()-1;j;j--){
			if (j+1 < (int)dp[i].size() && j < (int)dp[i-1].size())
				dp[i][j] = dp[i][j+1] | (dp[i-1][j] << b[j]);
			else if (j+1 < (int)dp[i].size())
				dp[i][j] = dp[i][j+1];
			else if (j < (int)dp[i-1].size())
				dp[i][j] = dp[i-1][j] << b[j];

			dp[i][j] &= B[i];
		}
	}

	for (int i=1;i<=S;i++) if (dp[i][1][S]) output(i, 1, S);
	printf("-1\n");
}

Compilation message (stderr)

cookies.cpp: In function 'int main()':
cookies.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
cookies.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d", a+i);
      |   ~~~~~^~~~~~~~~~~
cookies.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d", &m);
      |  ~~~~~^~~~~~~~~~
cookies.cpp:67:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  for (int i=1;i<=m;i++) scanf("%d", b+i);
      |                         ~~~~~^~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 45 / 45
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15