Submission #1132861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132861		duckindog	Topical (NOI23_topical)	C++17	100 / 100	318 ms	121576 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  int n, k; cin >> n >> k;

  vector<vector<int>> r(n + 1, vector<int>(k + 1)), u = r;
  for (int i = 1; i <= n; ++i) { 
    for (int j = 1; j <= k; ++j) cin >> r[i][j];
  }
  for (int i = 1; i <= n; ++i) { 
    for (int j = 1; j <= k; ++j) cin >> u[i][j];
  }

  vector<vector<pair<int, int>>> ad(k + 1);
  for (int i = 1; i <= n; ++i) { 
    for (int j = 1; j <= k; ++j) ad[j].push_back({i, r[i][j]});
  }

  for (int i = 1; i <= k; ++i) { 
    sort(ad[i].begin(), ad[i].end(), [](const auto& a, const auto& b) { 
      return a.second > b.second;
    });
  }
  
  vector<long long> p(k + 1);
  vector<int> cnt(n + 1);

  int answer = 0;
  for (int i = 1; i <= n; ++i) { 
    for (int j = 1; j <= k; ++j) { 
      while (ad[j].size() && ad[j].back().second <= p[j]) { 
        if (++cnt[ad[j].back().first] == k) {
          answer += 1;
          for (int t = 1; t <= k; ++t) p[t] += u[ad[j].back().first][t];
        }
        ad[j].pop_back();
      }
    }
  }

  cout << answer << "\n";
}

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