Submission #1286447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286447		lucian	Topical (NOI23_topical)	C++17	61 / 100	1093 ms	114068 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<vector<int>> r, u;

bool cmp(int a, int b){
	long long sa = 0, sb = 0;
	for(int j = 0; j < k; j++){
		sa += r[a][j];
		sb += r[b][j];
	}
	return sa < sb;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	r.assign(n, vector<int>(k));
	u.assign(n, vector<int>(k));
	vector<int> p(k, 0);
	vector<bool> done(n, false);
	vector<int> id(n);

	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			cin >> r[i][j];
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			cin >> u[i][j];
		}
	}

	for(int i = 0; i < n; i++){
		id[i] = i;
	}

	sort(id.begin(), id.end(), cmp);

	int completed = 0;
	bool progress = true;
	while(progress){
		progress = false;
		for(int ii = 0; ii < n; ii++){
			int i = id[ii];
			if(done[i]) continue;
			bool can = true;
			for(int j = 0; j < k; j++){
				if(p[j] < r[i][j]){
					can = false;
					break;
				}
			}
			if(can){
				done[i] = true;
				completed++;
				progress = true;
				for(int j = 0; j < k; j++){
					p[j] += u[i][j];
					if(p[j] > 1000000000){
						p[j] = 1000000000;
					}
				}
			}
		}
	}

	cout << completed;
}

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