oj.uz

Submission #790651

# Submission time Handle Problem Language Result Execution time Memory
790651 2023-07-23T04:38:10 Z qwerasdfzxcl Cookies (JOI23_cookies) C++17
0 / 100
 2 ms 1236 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
vector<bitset<30>> dp[15015];
bitset<30> 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);
	dp[0][m].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

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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Incorrect 0 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Runtime error 2 ms 1236 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 656 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 660 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Incorrect 1 ms 596 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Incorrect 0 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Incorrect 0 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Incorrect 0 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -