Submission #1199847

#TimeUsernameProblemLanguageResultExecution timeMemory
1199847ofozTopical (NOI23_topical)C++17
In queue
0 ms0 KiB
#include <bits/stdc++.h> #define int long long using namespace std; #define pi pair<int, int> void solve() { int n, m; cin >> n >> m; vector<vector<int>> grid(n, vector<int>(m)); vector<vector<int>> gain(n, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> grid[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> gain[i][j]; } } vector<set<pi>> ptrs(m); for (int i = 0; i < n; i++) { ptrs[0].insert({grid[i][0], i}); } vector<int> cur(m, 0); int res = 0; vector<int> finished; bool start = true; while (start || !finished.empty()) { start = false; for (int i : finished) { res++; for (int j = 0; j < m; j++) { cur[j] += gain[i][j]; } } finished.clear(); for (int k = 0; k < m; k++) { while (!ptrs[k].empty() && (*ptrs[k].begin()).first <= cur[k]) { int x, i; tie(x, i) = *ptrs[k].begin(); if (k == m-1) { finished.push_back(i); } else ptrs[k+1].insert({grid[i][k+1], i}); ptrs[k].erase(ptrs[k].begin()); } } } cout << res << endl; } signed main() { solve(); return 0; }