제출 #1102648

#제출 시각아이디문제언어결과실행 시간메모리
1102648xnqsTopical (NOI23_topical)C++17
12 / 100
374 ms291448 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(); it++) { auto [key, node] = *it; if (key > cap[pos]) { break; } if (node->pfx_cnt <= 0) { continue; } int tmp = search(node, cap, add, pos+1); ret += tmp; root->pfx_cnt -= tmp; } 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; int 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"; } 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; } 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) { 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...