Submission #873521

#	Time	Username	Problem	Language	Result	Execution time	Memory
873521		dsyz	Topical (NOI23_topical)	C++17	100 / 100	424 ms	98192 KiB

Main

//23 minutes
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,K;
	cin>>N>>K;
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq[K];
	ll need[N][K];
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j < K;j++){
			cin>>need[i][j];
			pq[j].push({need[i][j],i});
		}
	}
	ll gain[N][K];
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j < K;j++){
			cin>>gain[i][j];
		}
	}
	ll numoftopic[N];
	memset(numoftopic,0,sizeof(numoftopic));
	ll curtopic[K];
	memset(curtopic,0,sizeof(curtopic));
	queue<ll> can;
	ll sum = 0;
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j < K;j++){
			while(!pq[j].empty() && pq[j].top().first <= curtopic[j]){
				numoftopic[pq[j].top().second]++;
				if(numoftopic[pq[j].top().second] >= K){
					can.push(pq[j].top().second);
				}
				pq[j].pop();
			}
		}
		while(!can.empty()){
			sum++;
			ll x = can.front();
			for(ll j = 0;j < K;j++){
				curtopic[j] += gain[x][j];
			}
			can.pop();
		}
	}
	cout<<sum<<'\n';
}

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