Submission #1211457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211457		vtnoo	Topical (NOI23_topical)	C++20	100 / 100	549 ms	153916 KiB

Main

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>

#define pb push_back
#define snd second
#define fst first
#define forn(i,n) for(int i=0;i<n;++i)
#define forsn(i,s,n) for(int i=s; i<n; ++i)
#define all(x) x.begin(), x.end()
#define imp(x) for(auto __:x)cout<<__<<" "; cout<<endl;
#define sz(c) int((c).size())
#define mset(a,v) memset((a), (v), sizeof(a));

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

int main(){	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,k;cin>>n>>k;
	vector<vi> r(n, vi(k)), u(n, vi(k));
	forn(i,n)forn(j,k)cin>>r[i][j];
	forn(i,n)forn(j,k)cin>>u[i][j];
	vi p(k,0), cnt(n, 0);
	vector<vector<ii>> v(k);
	forn(j,k)forn(i,n)v[j].pb({r[i][j], i});
	forn(j,k)sort(all(v[j]), [](auto f, auto s){
		return f.fst<s.fst;
	});
	//~ cout<<"PASS"<<endl;
	vi last(k,0);
	forn(j,k){
		while(last[j]<n&&v[j][last[j]].fst<=p[j]){
			cnt[v[j][last[j]].snd]++;
			last[j]++;
		}
	}
	int ans=0;
	set<int> q;
	forn(i,n)if(cnt[i]==k)q.insert(i);
	while(!q.empty()){
		int i=*q.begin();
		q.erase(q.begin());
		ans++;
		forn(j,k)p[j]+=u[i][j];
		forn(j,k){
			while(last[j]<n&&v[j][last[j]].fst<=p[j]){
				cnt[v[j][last[j]].snd]++;
				if(cnt[v[j][last[j]].snd]==k){
					q.insert(v[j][last[j]].snd);
				}
				last[j]++;
			}
		}
	}
	cout<<ans<<endl;
}

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