Submission #1199851

#TimeUsernameProblemLanguageResultExecution timeMemory
1199851ofozCurtains (NOI23_curtains)C++20
0 / 100
0 ms396 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<priority_queue<pi>> ptrs(m); for (int i = 0; i < n; i++) { ptrs[0].push({-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].top()).first <= cur[k]) { int x, i; tie(x, i) = ptrs[k].top(); x = -x; if (k == m-1) { finished.push_back(i); } else ptrs[k+1].push({-grid[i][k+1], i}); ptrs[k].pop(); } } } cout << res << endl; } signed main() { solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...