Submission #1184815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184815		epicci23	Topical (NOI23_topical)	C++20	100 / 100	319 ms	86400 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

void _(){
  int n, k;
  cin >> n >> k;
  vector<array<int,2>> v[k+5];
  vector<int> freq(n+5,0);
  vector<int> art[n+5];
   
  queue<int> q;

  for(int i=1;i<=n;i++){
    bool ok = 1;
  	for(int j=1;j<=k;j++){
  	  int val;
  	  cin >> val;
  	  if(val > 0) ok = 0;
  	  v[j].push_back({val,i});
  	}

  	if(ok){
  	  q.push(i);
  	  freq[i] = k + 5;
  	}
  }	

  for(int i=1;i<=k;i++) sort(all(v[i]));
  vector<int> p(k+5,0),pw(k+5,0);

  for(int i=1;i<=n;i++){
    vector<int> xd(k+2,0);
    for(int j=1;j<=k;j++) cin >> xd[j];
    art[i] = xd;
  }

  int cnt = 0;

  while(!q.empty()){
    int c = q.front();
    q.pop();
    cnt++;

    for(int i=1;i<=k;i++){
      pw[i] += art[c][i];
      while(p[i] < n && pw[i] >= v[i][p[i]][0]){
        freq[v[i][p[i]][1]]++;
        if(freq[v[i][p[i]][1]] == k) q.push(v[i][p[i]][1]);
        p[i]++;
      }
    }
  }

  cout << cnt << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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