Submission #1214189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214189		salmon	Cookies (JOI23_cookies)	C++20	0 / 100	0 ms	328 KiB

cookies

#include <bits/stdc++.h>
using namespace std;

int N;
int M;
int lst[15100];
int B[15100];
int mox[15100];
bitset<3100> memo[15100];
priority_queue<pair<int,int>> pq;

int coonter(int i){
	while(!pq.empty()) pq.pop();
	
	for(int i = 1; i <= N; i++) pq.push({lst[i],i});
	
	int ans = 0;
	
	while(pq.size() >= i){
		ans++;
		
		vector<pair<int,int>> v;
		
		for(int k = 0; k < i; k++){
			v.push_back(pq.top());
			pq.pop();
		}
		
		for(pair<int,int> ii : v){
			if(ii.first != 1){
				pq.push({ii.first - 1, ii.second});
			}
		}
	}
	
	return ans;
}

int main(){
	
	scanf(" %d",&N);
	
	int big = 0;
	int b = 0;
	
	for(int i = 1; i <= N; i++){
		scanf(" %d",&lst[i]);
		big = max(lst[i],big);
		b += lst[i];
	}
	
	scanf(" %d",&M);
	
	for(int i = 1; i <= M; i++){
		scanf(" %d",&B[i]);
		mox[i] = coonter(B[i]);
	}
	
	B[M + 1] = b + 1;
	
	memo[0][0] = 1;
	
	for(int j = 0; j < N; j++){
	for(int k = 0; k < mox[j]; k++){
	for(int i = b; i >= B[j]; i--){
		memo[i] |= (memo[i-B[j]]<<1);
		}
	}
	}
	
	int ans = -1;
	
	for(int i = big; i <= b; i++){
		if((int)memo[b][i]){
			ans = i;
			break;
		}
	}
	
	if(ans == -1){
		printf("%d\n",ans);
	}
	else{
		while(!pq.empty()) pq.pop();
	
		for(int i = 1; i <= N; i++){
			pq.push({lst[i],i});
		}
		
		int pos = b;
		
		printf("%d\n",ans);
		
		for(int i = ans - 1; i >= 0; i--){
			for(int j = 1; j <= M; j++){
				if(memo[pos - B[j]][i] ){
					pos = pos - B[j];
					printf("%d ",B[j]);
					
					vector<pair<int,int>> vii;
					for(int k = 0; k < B[j]; k++){
						vii.push_back(pq.top());
						pq.pop();
					}
					
					for(pair<int,int> ii : vii){
						if(ii.first != 1){
							pq.push({ii.first - 1, ii.second});
						}
						printf("%d ",ii.second);
					}
					printf("\n");
					
					break;
				}
			}
		}
	}
}

Compilation message (stderr)

cookies.cpp: In function 'int main()':
cookies.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
cookies.cpp:47:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
cookies.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf(" %d",&M);
      |         ~~~~~^~~~~~~~~~
cookies.cpp:55:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |                 scanf(" %d",&B[i]);
      |                 ~~~~~^~~~~~~~~~~~~

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