Submission #1162022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162022		veehj	Topical (NOI23_topical)	C++20	100 / 100	542 ms	86584 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
ll n, k, ans;
vector<vector<ll>> u;
vector<vector<pair<ll, ll>>> r;
vector<bool> vist;
queue<ll> wit;
vector<ll> lst, cnt, curr;

void updt(){
  for(ll i=0; i<k; i++){
    ll nw=lst[i];
    for(; nw<n; nw++){
      if(r[i][nw].fi<=curr[i]){
        cnt[r[i][nw].se]++;
        if(cnt[r[i][nw].se]==k) wit.push(r[i][nw].se);
      } else break;
    }
    lst[i]=nw;
  }
}

void f(){
  cin >> n >> k;
  ans=0;
  u.assign(n, vector<ll>(k, 0));
  r.assign(k, vector<pair<ll, ll>>(n, {0, 0}));
  vist.assign(n, 0);
  lst.assign(k, 0);
  cnt.assign(n, 0);
  curr.assign(k, 0);
  for(ll i=0; i<n; i++){
    for(ll j=0; j<k; j++) {cin >> r[j][i].fi; r[j][i].se=i; }
  }
  for(auto& uu : r) sort(all(uu));
  for(auto& uu : u) for(auto & uuu : uu) cin >> uuu;
  while(1){
    updt();
    if(wit.empty()){
      cout << ans;
      return;
    }
    while(!wit.empty()){
      ans++;
      ll ad=wit.front();
      wit.pop();
      for(ll i=0; i<k; i++) curr[i]+=u[ad][i];
    }
  }
}

int main() {
  int tc=1; 
  // cin >> tc;
  for(int i=1; i<=tc; i++){
    // cout << '#' << i << endl;
    f();
    if(i!=tc) cout << endl;
  }
}

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