Submission #1285102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285102		nlsosad	Topical (NOI23_topical)	C++20	100 / 100	769 ms	166408 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int cnt[1000001];
vector<pair<int, int>> luu[1000001];
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<vector<int>> r(n+1, vector<int>(k+1)), u(n+1, vector<int>(k+1));
	for (int i = 1;i<=n;++i){
		for (int j = 1;j<=k;++j){
			cin >> r[i][j];
			if(r[i][j]==0)cnt[i]++;
			else luu[j].push_back({r[i][j], i});
		}
	}
	for (int i = 1;i<=k;++i){
		sort(luu[i].begin(), luu[i].end(), [](pair<int, int> p, pair<int, int> q){
			return p>q;
		});
	}
	for (int i = 1;i<=n;++i){
		for (int j = 1;j<=k;++j){
			cin >> u[i][j];
		}
	}
	using state = pair<int, int>;
	priority_queue<state> pq;
	for (int i = 1;i<=n;++i){
		pq.push({cnt[i], i});
		// cout << cnt[i] << ' ' << i << '\n';
	}
	// cout << '\n';
	vector<int> p(k+1, 0);
	int res = 0;
	while(!pq.empty()){
		auto [d, i] = pq.top();
		pq.pop();
		if(d!=cnt[i])continue;
		// cout << d << ' ' << i << '\n';
		if(d!=k){
			cout <<res;
			return 0;
		}else{
			for (int j = 1;j<=k;++j){
				p[j] += u[i][j];
				while(!luu[j].empty()){
					auto [x, y] = luu[j].back();
					if(p[j] >= x){
						cnt[y]++;
						pq.push({cnt[y], y});
						luu[j].pop_back();
					}else break;
				}
			}
			res++;
		}
	}
	cout << res;
}

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