Submission #831381

#	Time	Username	Problem	Language	Result	Execution time	Memory
831381		CSQ31	Cookies (JOI23_cookies)	C++17	100 / 100	141 ms	235336 KiB

cookies

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 15001;
vector<bitset<MAXN>>dp[MAXN]; //this many items
bitset<MAXN>full[MAXN];
int a[MAXN],b[MAXN+1],c[MAXN],cnt[MAXN];
int main()
{
	owo
	int n,m,s = 0;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		cnt[a[i]]++;
		s+=a[i];
	}
	int cur = n,sum = 0;
	for(int i=1;i<MAXN;i++){
		sum+=cnt[i]*i;
		cur-=cnt[i];
		c[i] = sum + cur*i;
	}
	int prev = 0;
	for(int i=1;i<MAXN;i++){
		full[i] = full[i-1];
		while(prev<=c[i]){
			full[i][prev] = 1;
			prev++;
		}	
		prev--;
	}
	cin>>m;
	for(int i=0;i<m;i++)cin>>b[i];
	sort(b,b+m,greater<int>());
	
	dp[0].resize(1);
	dp[0][0][0] = 1;
	for(int i=0;i<m;i++){
		int k = s/b[i];
		dp[i+1].resize(k+1);
		for(int j=0;j<sz(dp[i]);j++)dp[i+1][j] = dp[i][j];
		for(int j=1;j<=k;j++){
			dp[i+1][j] |= dp[i+1][j-1] << b[i];
			dp[i+1][j] &= full[j];
		}
	}
	vector<int>item;
	cur = -1;
	for(int i=0;i<sz(dp[m]);i++){
		if(dp[m][i][s]){
			cur = i;
			break;
		}
	}
	
	if(cur==-1){
		cout<<-1;
		return 0;
	}
	for(int i=m;i>0;i--){
		//cout<<cur<<" "<<sz(dp[i])<<'\n';
		while(s >= b[i-1] && cur){
			if(dp[i][cur][s]){
				if(dp[i][cur-1][s-b[i-1]]){
					item.pb(b[i-1]);
					cur--;
					s-=b[i-1];
				}else{
					if(dp[i-1][cur-1][s-b[i-1]]){
						item.pb(b[i-1]);
						cur--;
						s-=b[i-1];
					}
					break;					
				}
			}
			
		}
		
	}
	multiset<pii,greater<pii>>ss;
	for(int i=0;i<n;i++)ss.insert({a[i],i});
	
	cout<<sz(item)<<'\n';
	for(int x:item){
		vector<int>sol,addback;
		for(int i=0;i<x;i++){
			int j = ss.begin()->se;
			ss.erase(ss.begin());
			sol.pb(j+1);
			a[j]--;
			if(a[j])addback.pb(j);
		}
		for(int x:addback)ss.insert({a[x],x});
		cout<<x<<" ";
		for(int x:sol)cout<<x<<" ";
		cout<<'\n';
		
	}
	
}

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