Submission #1214238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214238		PenguinsAreCute	Cookies (JOI23_cookies)	C++17	6 / 100	65 ms	47176 KiB

cookies

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
int main() {
	int n, tot = 0;
	cin >> n;
	int a[n];
	priority_queue<pair<int,int>> pq;
	for(int i=0;i<n;i++) {
		cin >> a[i];
		tot += a[i];
		pq.push({a[i],i});
	}
	sort(a,a+n);
	auto add = [&pq](int s) {
		vector<int> ans(s,0);
		vector<pair<int,int>> used;
		for(int i=0;i<s;i++) {
			auto [cnt, idx] = pq.top();
			assert(cnt > 0);
			pq.pop();
			used.push_back({cnt-1,idx});
			ans[i] = idx;
		}
		for(auto i: used)
			pq.push(i);
		return ans;
	};
	int m;
	cin >> m;
	int b[m];
	for(int i=0;i<m;i++)
		cin >> b[i];
	bool ok[n];
	memset(ok,0,sizeof(ok));
	for(int i=0;i<m;i++)
		ok[n-b[i]] = 1;
	bitset<3001> dp[2][tot+1];
	bitset<3001> store[n/2+1][tot+1];
	dp[0][0][0] = store[0][0][0] = 1;
	for(int i=1;i<=n;i++) {
		for(int j=0;j<a[i-1];j++)
			dp[i&1][j] = dp[1^i&1][j] << (a[i-1] - j);
		for(int j=a[i-1];j<=tot;j++)
			dp[i&1][j] = dp[1^i&1][j] >> (j - a[i-1]);
		if(ok[i-1])
			for(int j=1;j<=tot;j++)
				dp[i&1][j] |= (dp[i&1][j-1] >> 1);
		if(!(i%2))
			memcpy(store[i/2],dp[i&1],sizeof(store[i/2]));
	}
	for(int j=0;j<=tot;j++)
		if(dp[n&1][j][0]) {
			cout << j << "\n";
			int i0 = n, j0 = j, k0 = 0;

			bitset<3001> comp[2][tot+1];
			memcpy(comp[0],store[n/2],sizeof(comp[0]));
			int base = 2 * (n / 2);
			for(int i=1;i<=(n&1);i++) {
				for(int j=0;j<a[base+i-1];j++)
					comp[i][j] = comp[i-1][j] << (a[base+i-1] - j);
				for(int j=a[i-1];j<=tot;j++)
					comp[i][j] = comp[i-1][j] >> (j - a[base+i-1]);
				if(ok[base+i-1])
					for(int j=1;j<=tot;j++)
						comp[i][j] |= (comp[i][j-1] >> 1);
			}

			while(i0) {
				if(j0 && k0 < tot && ok[i0-1] && comp[i0%2][j0-1][k0+1]) {
					j0 -= 1, k0 += 1;
					vector<int> ans = add(n-i0+1);
					cout << n-i0+1 << " ";
					for(auto e: ans)
						cout << e+1 << " ";
					cout << "\n";
				} else {
					k0 -= (a[--i0] - j0);
					if(i0 & 1) {
						memcpy(comp[0],store[i0/2],sizeof(comp[0]));
						int base = i0 - 1;
						for(int i=1;i<=1;i++) {
							for(int j=0;j<a[base+i-1];j++)
								comp[i][j] = comp[i-1][j] << (a[base+i-1] - j);
							for(int j=a[i-1];j<=tot;j++)
								comp[i][j] = comp[i-1][j] >> (j - a[base+i-1]);
							if(ok[base+i-1])
								for(int j=1;j<=tot;j++)
									comp[i][j] |= (comp[i][j-1] >> 1);
						}
					}
				}
			}
			return 0;
		}
	cout << -1;
}

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