제출 #1102433

#제출 시각아이디문제언어결과실행 시간메모리
1102433xnqsTopical (NOI23_topical)C++17
12 / 100
1088 ms347664 KiB
#include <iostream> #include <fstream> #include <vector> #include <queue> #include <utility> #include <algorithm> #include <map> #include <unordered_set> 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::unordered_set<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(val); } int search(TrieNode* root, const std::vector<int>& cap, std::vector<int>& 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; } if (node->pfx_cnt <= 0) { ++it; continue; } int tmp = search(node, cap, add, pos+1); ret += tmp; root->pfx_cnt -= tmp; if (!node->pfx_cnt) { it = root->next.erase(it); } else { ++it; } } return ret; } 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]; } } for (int i = 0; i < x; i++) { add_word(root, arr[i].req, i); } std::vector<int> cap(k, 0); int ans = 0; while (1) { std::vector<int> add(k, 0); int nodes = search(root, cap, add); if (!nodes) { nodes = search(root, cap, add); // try again bc yes break; } if (!nodes) { break; } ans += nodes; for (int i = 0; i < k; i++) { cap[i] += add[i]; } } std::cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...