oj.uz

답안 #1102424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1102424 2024-10-18T06:11:30 Z xnqs Topical (NOI23_topical) C++17
12 / 100
 1000 ms 282200 KB 
#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;
	root->pfx_cnt = 0;
	for (const auto& [key, node] : root->next) {
		//std::cout << key << " " << cap[pos] << "\n";
		if (key > cap[pos]) {
			root->pfx_cnt += node->pfx_cnt;
			continue;
		}
		if (node->pfx_cnt <= 0) {
			root->pfx_cnt += node->pfx_cnt;
			continue;
		}

		ret += search(node, cap, add, pos+1);
		root->pfx_cnt += node->pfx_cnt;
	}

	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) {
			break;
		}

		ans += nodes;
		for (int i = 0; i < k; i++) {
			cap[i] += add[i];
		}
	}

	std::cout << ans << "\n";
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 2384 KB Output is correct
4 Correct 375 ms 282200 KB Output is correct
5 Correct 361 ms 282184 KB Output is correct
6 Correct 391 ms 282184 KB Output is correct
7 Correct 216 ms 203848 KB Output is correct

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Incorrect 5 ms 2384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 18 ms 4688 KB Output is correct
4 Correct 369 ms 44840 KB Output is correct
5 Execution timed out 1062 ms 45028 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 2384 KB Output is correct
4 Correct 375 ms 282200 KB Output is correct
5 Correct 361 ms 282184 KB Output is correct
6 Correct 391 ms 282184 KB Output is correct
7 Correct 216 ms 203848 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Incorrect 5 ms 2384 KB Output isn't correct
15 Halted 0 ms 0 KB -