Submission #1184823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184823		SalihSahin	Topical (NOI23_topical)	C++20	100 / 100	358 ms	136476 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define pb push_back
using namespace std;

const int inf = 1e9;
const int N = 2e5 + 20;

int32_t main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n, m;
  cin>>n>>m;
  vector<vector<int> > r(n, vector<int>(m)), u(n, vector<int>(m));
  vector<int> cnt(n), p(m);
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        cin>>r[i][j];
    }
  }

   for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        cin>>u[i][j];
    }
   }

   vector<pair<int, int> > col[m];

   for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        col[j].pb({r[i][j], i});
    }
   }
   for(int i = 0; i < m; i++){
    sort(col[i].begin(), col[i].end());
   }
   vector<int> ind(m);
   queue<int> add;

   for(int i = 0; i < m; i++){
    while(ind[i] < n && col[i][ind[i]].first <= p[i]){
        cnt[col[i][ind[i]].second]++;
        if(cnt[col[i][ind[i]].second] == m) add.push(col[i][ind[i]].second);
        ind[i]++;
    }
   }

   int ans = 0;
   
   while(!add.empty()){
    int x = add.front();
    add.pop();
    ans++;

    for(int i = 0; i < m; i++){
        p[i] += u[x][i];
        while(ind[i] < n && col[i][ind[i]].first <= p[i]){
            cnt[col[i][ind[i]].second]++;
            if(cnt[col[i][ind[i]].second] == m) add.push(col[i][ind[i]].second);
            ind[i]++;
        }
    }
   }

   cout<<ans<<endl;
   return 0;
}

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