Submission #1285146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285146		duyanhchupapi	Topical (NOI23_topical)	C++20	100 / 100	559 ms	125036 KiB

Main

#include <bits/stdc++.h>
using namespace std; 
using ll = long long; 
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, k, ans, cur[N], sum[N];
vector<vector<int>> u, r, id;
ll p[N];

int main() { 
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
	cin >> n >> k;
	u.resize(n+1, vector<int> (k+1,0)), r.resize(n+1, vector<int> (k+1,0));
	id.resize(k+1, vector<int> (n + 1));
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=k;++j) cin >> r[i][j], id[j][i] = i;
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=k;++j) cin >> u[i][j];
	}
	for(int i=1;i<=k;++i) {
		sort(id[i].begin()+1,id[i].begin()+n+1, [&](int x, int y) {
			return r[x][i] < r[y][i];
		});
		cur[i] = 1;
	}
	
	while(1) {
		vector <int> luu;
		for(int i=1;i<=k;++i) {
			while(cur[i] <= n && p[i] >= r[id[i][cur[i]]][i]) {
				sum[id[i][cur[i]]]++;
				if(sum[id[i][cur[i]]] == k) luu.push_back(id[i][cur[i]]);
				cur[i]++;
			}
		}
		if(luu.empty()) break;
		for(int idd : luu) {
			for(int i=1;i<=k;++i) p[i] += u[idd][i];
			ans++;
		}
 	}
 	/*for(int i=1;i<=k;++i) {
 		cout << '\n';
 		for(int j=1;j<=n;++j) {
 			for(int t=1;t<=k;++t) cout << r[id[i][j]][t] << ' '; cout << '\n';
		 }
	}*/
 	//for(int i=1;i<=k;++i) cout << cur[i] << ' ';  cout << '\n';
	cout << ans;
 	return 0;
}

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