oj.uz

Submission #789236

# Submission time Handle Problem Language Result Execution time Memory
789236 2023-07-21T08:33:36 Z 박상훈(#10042) Cookies (JOI23_cookies) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, m, L, a[100100], a2[100100], b[100100], valid[100100];
int par[3030][3030];

void output(int x, int y){
	vector<int> buf;
	while(x && y){
		assert(par[x][y]);
		buf.push_back(par[x][y]);
		// printf("ok %d %d -> %d\n", x, y, par[x][y]);
		x--;
		y -= b[buf.back()];
	}

	assert(x==0 && y==0);

	sort(buf.begin(), buf.end());
	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:buf){
		x = b[x];
		assert((int)pq.size() >= x);
		ans.emplace_back();
		vector<pair<int, int>> nxt;

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

		for (auto &p:nxt) 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(){
	scanf("%d", &n);
	for (int i=1;i<=n;i++){
		scanf("%d", a+i);
		a2[i] = a[i];
		L += a[i];
	}

	sort(a2+1, a2+n+1, greater<int>());
	for (int i=1;i<=L;i++){
		for (int j=1;j<=n;j++) valid[i] += min(a2[j], i);
	}

	printf(" %d %d\n", valid[0], valid[1]);

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

	par[0][0] = -1;

	for (int j=1;j<=m;j++){
		for (int i=0;i<L;i++){
			for (int sum=0;sum+b[j]<=min(valid[i]+b[j], valid[i+1]);sum++) if (par[i][sum] && !par[i+1][sum+b[j]]){
				par[i+1][sum+b[j]] = j;
			}
		}

		// if (j==1) printf(" %d\n", par[1][6]);
		// if (j==2) printf(" %d\n", par[2][8]);
		// if (j==2) printf(" %d\n", par[7][L]);
	}

	for (int i=1;i<=L;i++) if (par[i][L]) output(i, L);
	printf("-1\n");
	return 0;
}

Compilation message

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Number of cookies does not match with A_i
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Number of cookies does not match with A_i
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Number of cookies does not match with A_i
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Number of cookies does not match with A_i
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Number of cookies does not match with A_i
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Number of cookies does not match with A_i
2 Halted 0 ms 0 KB -