Submission #1300663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300663		SmuggingSpun	Topical (NOI23_topical)	C++20	100 / 100	381 ms	123324 KiB

Main

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
const int INF = 1e9 + 5;
void add(int& a, int b){
	if((a += b) > INF){
		a = INF;
	}
}
int n, k;
vector<vector<int>>r, u;
namespace sub1{
	void solve(){
		cout << int(*max_element(r[0].begin(), r[0].end()) == 0);
	}
}
namespace sub2{
	void solve(){
		vector<int>skill(k, 0);
		vector<bool>used(n, false);
		while(true){
			bool flag = true;
			for(int i = 0; i < n; i++){
				if(!used[i]){
					flag = false;
					for(int j = 0; j < k; j++){
						if(skill[j] < r[i][j]){
							flag = true;
							break;
						}
					}
					if(!flag){
						used[i] = true;
						for(int j = 0; j < k; j++){
							add(skill[j], u[i][j]);
						}
						break;
					}
				}
			}
			if(flag){
				break;
			}
		}
		cout << count(used.begin(), used.end(), true);
	}
}
namespace sub34{
	void solve(){
		vector<vector<pair<int, int>>>p(k);
		queue<int>q;
		vector<int>skill(k, 0), cnt(n, k);
		for(int i = 0; i < n; i++){
			bool flag = true;
			for(int j = 0; j < k; j++){
				p[j].push_back(make_pair(r[i][j], i));
				if(r[i][j] > 0){
					flag = false;
				}
			}
			if(flag){
				q.push(i);
				cnt[i] = 0;
			}
		}
		for(int i = 0; i < k; i++){
			sort(p[i].begin(), p[i].end(), greater<pair<int, int>>());
		}
		int ans = 0;
		while(!q.empty()){
			int i = q.front();
			q.pop();
			ans++;
			for(int j = 0; j < k; j++){
				add(skill[j], u[i][j]);
				while(!p[j].empty() && p[j].back().first <= skill[j]){
					if(--cnt[p[j].back().second] == 0){
						q.push(p[j].back().second);
					}
					p[j].pop_back();
				}
			}
		}
		cout << ans;
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> k;
	r.resize(n, vector<int>(k));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			cin >> r[i][j];
		}
	}
	u.resize(n, vector<int>(k));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			cin >> u[i][j];
		}
	}
	if(n == 1){
		sub1::solve();
	}
	else if(max(n, k) <= 100){
		sub2::solve();
	}
	else{
		sub34::solve();
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:91:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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