Submission #788127

#	Time	Username	Problem	Language	Result	Execution time	Memory
788127		model_code	Cookies (JOI23_cookies)	C++17	100 / 100	268 ms	325988 KiB

cookies

/*
	FULL-SCORE SOLUTION OF "COOKIES"
	- Dynamic programming & construction of answer using greedy algorithm
	- Speedup DP using "harmonic series"
	- Speedup DP using bitset
	- Time Complexity: O(sumA^2 log N) * 1/64
*/

#include <queue>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<vector<int> > solve(int N, int M, const vector<int>& A, const vector<int>& B) {
	// step #1. preparation
	vector<int> SA = A;
	sort(SA.begin(), SA.end(), greater<int>());
	vector<int> LA(N + 1);
	for (int i = 0; i < N; i++) {
		LA[i + 1] = LA[i] + SA[i];
	}
	int S = LA[N];
	vector<bool> changer(N + 1, false);
	for (int i = 0; i < M; i++) {
		changer[B[i]] = true;
	}

	// step #2. dynamic programming
	bitset<15001> allone = ~bitset<15001>();
	vector<vector<bitset<15001> > > dp(N + 1); // dp[pos][height][sum], height <= S / pos
	for (int i = 0; i <= N; i++) {
		dp[i] = vector<bitset<15001> >(i != 0 ? S / i + 1 : S + 1);
	}
	dp[N][0][S] = 1;
	for (int i = N; i >= 0; i--) {
		for (int j = 0; j <= (i != 0 ? S / i : S); j++) {
			if (i != N && j <= S / (i + 1)) {
				dp[i][j] |= dp[i + 1][j] >> j;
			}
			if (changer[i] && j != 0) {
				dp[i][j] |= dp[i][j - 1];
			}
			dp[i][j] &= allone << LA[i];
		}
	}
	int min_boxes = -1;
	for (int i = 0; i <= S; i++) {
		if (dp[0][i][0]) {
			min_boxes = i;
			break;
		}
	}
	if (min_boxes == -1) {
		return vector<vector<int> >();
	}

	// step #3. restoration
	vector<int> boxsize;
	int px = 0, py = min_boxes, pz = 0;
	while (!(px == N && py == 0)) {
		if (px != N && pz + py <= S && dp[px + 1][py][pz + py]) {
			px += 1;
			pz += py;
		}
		else {
			py -= 1;
			boxsize.push_back(px);
		}
	}

	// step #4. greedy algorithm
	vector<vector<int> > answer;
	priority_queue<pair<int, int> > que;
	for (int i = 0; i < N; i++) {
		que.push(make_pair(A[i], i));
	}
	vector<int> remA = A;
	for (int s : boxsize) {
		vector<int> pack(s, -1);
		for (int j = 0; j < s; j++) {
			pair<int, int> u = que.top();
			que.pop();
			pack[j] = u.second;
		}
		for (int j = 0; j < s; j++) {
			remA[pack[j]] -= 1;
			if (remA[pack[j]] != 0) {
				que.push(make_pair(remA[pack[j]], pack[j]));
			}
		}
		answer.push_back(pack);
	}

	return answer;
}

int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	int M;
	cin >> M;
	vector<int> B(M);
	for (int i = 0; i < M; i++) {
		cin >> B[i];
	}
	vector<vector<int> > answer = solve(N, M, A, B);
	if (answer.empty()) {
		cout << -1 << '\n';
	}
	else {
		cout << answer.size() << endl;
		for (vector<int> v : answer) {
			cout << v.size();
			for (int i : v) {
				cout << ' ' << i + 1;
			}
			cout << '\n';
		}
	}
	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