제출 #1312387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312387		sakuda00	Topical (NOI23_topical)	C++20	100 / 100	873 ms	130952 KiB

Main

#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <queue>
#include <deque>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
using ll = long long;
int main() {
	int N, K;cin >> N >> K;
	vector<vector<ll>> A(N, vector<ll>(K, 0));
	auto B = A;
	vector<vector<pair<ll, int>>> ST(K);
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < K;j++) {
			cin >> A[i][j];
			ST[j].push_back({A[i][j], i});
		}
	}
	for (int i = 0;i < N;i++) for (int j = 0;j < K;j++) cin >> B[i][j];
	for (int i = 0;i < K;i++) sort(ST[i].begin(), ST[i].end());
	vector<int> IT(K, 0);
	vector<ll> now(K, 0);
	vector<int> seen(N, 0);
	int res = 0;
	int times = 0;
	while (true) {
		queue<int> nxt;
		for (int i = 0;i < K;i++) {
			int it = IT[i];
			while (it < N && ST[i][it].first <= now[i]) {
				times++;
				int id = ST[i][it].second;
				seen[id]++;
				if (seen[id] == K) nxt.push(id);
				it++;
			}
			IT[i] = it;
		}
		if (nxt.empty()) break;
		while (!nxt.empty()) {
			int id = nxt.front();
			nxt.pop();
			for (int j = 0;j < K;j++) now[j] += B[id][j];
			res++;
		}
	}
	cout << res << endl;

}

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