제출 #1102683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102683		xnqs	Topical (NOI23_topical)	C++17	61 / 100	1065 ms	117832 KiB

Main

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <numeric>
#include <list>

struct Module {
	int n;
	std::vector<int> req;
	std::vector<int> add;
 
	Module(int n = 0): n(n) {
		req.assign(n, 0);
		add.assign(n, 0);
	}
};
 
struct TrieNode {
	std::vector<int> idx;
	int pfx_cnt = 0;
	std::map<int, TrieNode*> next;
 
	~TrieNode() {
		for (auto& [key, val] : next) {
			if (val) {
				delete val;
			}
		}
		next.clear();
	}
};
 
int x, k;
std::vector<Module> arr;
TrieNode* root = new TrieNode;
 
void add_word(TrieNode* root, const std::vector<int>& word, int val) {
	for (int i = 0; i < k; i++) {
		if (!root->next[word[i]]) {
			root->next[word[i]] = new TrieNode;
		}
 
		root = root->next[word[i]];
		++root->pfx_cnt;
	}
 
	root->idx.emplace_back(val);
}
 
int search(TrieNode* root, const std::vector<int64_t>& cap, std::vector<int64_t>& add, int pos = 0) {
	if (pos == k) {
		for (int i = 0; i < k; i++) {
			for (const auto& j : root->idx) {
				add[i] += arr[j].add[i];
			}
		}
 
		int ret = (int)root->idx.size();
		root->pfx_cnt -= root->idx.size();
		root->idx.clear();
		return ret;
	}
 
	int ret = 0;
	for (auto it = root->next.begin(); it != root->next.end();) {
		auto [key, node] = *it;
		if (key > cap[pos]) {
			break;
		}
 
		int tmp = search(node, cap, add, pos+1);
		ret += tmp;
		root->pfx_cnt -= tmp;
 
		if (node->pfx_cnt <= 0) {
			it = root->next.erase(it);
		}
		else {
			++it;
		}
	}
 
	return ret;
}
 
void solve_k1() {
	std::sort(arr.begin(), arr.end(), [](const Module& a, const Module& b) {
		return a.req[0] < b.req[0];
	});
 
	int ans = 0;
	int64_t curr_skill = 0;
	for (const auto& it : arr) {
		int req = it.req[0];
		int add = it.add[0];
 
		if (curr_skill < req) {
			break;
		}
 
		++ans;
		curr_skill += add;
	}
 
	std::cout << ans << "\n";
}
 
void solve_not_legit_at_all() {
	std::vector<int> tmp(x);
	std::iota(tmp.begin(),tmp.end(),0);
	std::sort(tmp.begin(),tmp.end(),[&](int a, int b) {
		return arr[a].req[0] < arr[b].req[0];
	});

	std::list<int> idx(tmp.begin(),tmp.end());
	int ans = 0;
	std::vector<int64_t> cap(k,0);
	while (!idx.empty()) {
		int old_ans = ans;
		for (auto it = idx.begin(); it != idx.end();) {
			int val = *it;
			if (arr[val].req[0] > cap[0]) {
				break;
			}

			bool ok = 1;
			for (int i = 1; i < k; i++) {
				if (arr[val].req[i] > cap[i]) {
					ok = 0;
					break;
				}
			}

			if (!ok) {
				++it;
				continue;
			}

			ans += 1;
			for (int i = 0; i < k; i++) {
				cap[i] += arr[val].add[i];
			}

			it = idx.erase(it);
		}

		if (ans == old_ans) {
			break;
		}
	}
 
	std::cout << ans << "\n";
}
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
 
	std::cin >> x >> k;
	arr.reserve(x);
	for (int i = 0; i < x; i++) {
		arr.emplace_back(k);
		for (int j = 0; j < k; j++) {
			std::cin >> arr[i].req[j];
		}
	}
	for (int i = 0; i < x; i++) {
		for (int j = 0; j < k; j++) {
			std::cin >> arr[i].add[j];
		}
	}
 
	if (k==1) {
		solve_k1();
		return 0;
	}
	if (k>=2) {
		solve_not_legit_at_all();
		return 0;
	}
	
	for (int i = 0; i < x; i++) {
		add_word(root, arr[i].req, i);
	}
 
	std::vector<int64_t> cap(k, 0);
	int ans = 0;
	while (1) {
		std::vector<int64_t> add(k, 0);
		int nodes = search(root, cap, add);
		if (!nodes) {
			break;
		}
 
		ans += nodes;
		for (int i = 0; i < k; i++) {
			cap[i] += add[i];
		}
	}
 
	std::cout << ans << "\n";
}

• Subtask 1: 12 / 12
• Subtask 2: 28 / 28
• Subtask 3: 21 / 21
• Subtask 4: 0 / 39