Submission #789080

#	Time	Username	Problem	Language	Result	Execution time	Memory
789080		moonrabbit2	Cookies (JOI23_cookies)	C++17	100 / 100	413 ms	55972 KiB

cookies

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#define fi first
#define se second
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using db=double;
const int N=15005;
int n,a[N],m,b[N];
int k,mx,lim[N],cnt[N];
bitset<N> dp[N],L[N];
int l,c[N];
pii cur[N],ncur[N];
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		k+=a[i];
		mx=max(mx,a[i]);
		cnt[a[i]]++;
	}
	for(int s1=n,s2=0,i=1;i<=k;i++){
		s1-=cnt[i];
		s2+=cnt[i]*i;
		lim[i]=i*s1+s2;
		for(int j=0;j<=lim[i];j++) L[i][j]=1;
	}
	cin>>m;
	for(int i=1;i<=m;i++) cin>>b[i];
	dp[0][0]=1;
	for(int i=m;i>=1;i--){
		for(int t=1;t*b[i]<=k;t++) dp[t]=(dp[t]|(dp[t-1]<<b[i]))&L[t];
		//for(int s=t*b[i];s<=lim[t];s++) if(dp[t-1][s-b[i]]) dp[t][s]=true;
	}
	for(int t=mx;t<=k;t++) if(dp[t][k]){
		l=t;
		break;
	}
	if(!l){
		cout<<"-1\n";
		return 0;
	}
	for(int t=l,s=k,i=1;t>=1;t--){
		while(!dp[t-1][s-b[i]]) i++;
		c[t]=b[i];
		s-=b[i];
	}
	sort(c+1,c+1+l,greater<>());
	for(int i=1;i<=n;i++) cur[i]=pii(a[i],i);
	sort(cur+1,cur+1+n,greater<>());
	cout<<l<<"\n";
	for(int t=1;t<=l;t++){
		cout<<c[t]<<" ";
		for(int i=1;i<=c[t];i++){
			cout<<cur[i].se<<" ";
			cur[i].fi--;
			assert(cur[i].fi>=0);
		}
		cout<<"\n";
		for(int i=1,j=c[t]+1;i<=c[t]||j<=n;){
			if(j>n||(i<=c[t]&&cur[i].fi>cur[j].fi)){
				ncur[i+j-c[t]-1]=cur[i];
				i++;
			} else{
				ncur[i+j-c[t]-1]=cur[j];
				j++;
			}
		}
		for(int i=1;i<=n;i++) cur[i]=ncur[i];
	}
	return 0;
}

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