제출 #1369509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369509		gohchingjayk	Topical (NOI23_topical)	C++20	100 / 100	240 ms	85384 KiB

Main

#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

using ii = pair<int, int>;
using iii = pair<ii, int>;

constexpr int MAXN = 1'000'000 + 5;
constexpr int INF = 1e18 + 5;
constexpr int LOG = 20;

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);

	int N, K; cin >> N >> K;
	vector<vector<ii>> per_topic(K, vector<ii>(N));
	vector<vector<int>> bonus(N, vector<int>(K));
	vector<int> curr(K);
	vector<int> cnt(N);

	vector<int> addable;
	
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < K; ++j) {
			int x; cin >> x;
			per_topic[j][i] = ii{x, i};
		}
	}
	
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < K; ++j) {
			cin >> bonus[i][j];
		}
	}
	
	for (int i = 0; i < K; ++i) sort(per_topic[i].begin(), per_topic[i].end(), greater<ii>{});

	int ans = 0;
	while (true) {
		for (int i = 0; i < K; ++i) {
			while (!per_topic[i].empty() && per_topic[i].back().first <= curr[i]) {
				int j = per_topic[i].back().second;
				per_topic[i].pop_back();
				cnt[j]++;
				if (cnt[j] == K) addable.emplace_back(j);
			}
		}
		
		if (addable.empty()) break;
		
		for (int j : addable) {
			ans++;
			for (int i = 0; i < K; ++i) {
				curr[i] += bonus[j][i];
			}
		}
		
		addable.clear();
	}

	cout << ans;
}

• 서브태스크 1: 12 / 12
• 서브태스크 2: 28 / 28
• 서브태스크 3: 21 / 21
• 서브태스크 4: 39 / 39