Submission #1272789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272789		ortsac	Topical (NOI23_topical)	C++20	100 / 100	915 ms	697580 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

int32_t main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> r(n, vector<int>(k));
    vector<vector<int>> u(n, vector<int>(k));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) cin >> r[i][j];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) cin >> u[i][j];
    }
    vector<deque<pii>> pr(k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) pr[j].push_back({r[i][j], i});
    }
    for (int i = 0; i < k; i++) sort(pr[i].begin(), pr[i].end());
    vector<int> qtd(n);
    vector<int> curr(k);
    vector<int> todos;
    bool ok = 1;
    int ans = 0;
    while (ok) {
        ok = 0;
        for (int i = 0; i < k; i++) {
            while (!pr[i].empty() && (pr[i].front().fr <= curr[i])) {
                qtd[pr[i].front().se]++;
                if (qtd[pr[i].front().se] == k) todos.push_back(pr[i].front().se);
                pr[i].pop_front();
            }
        }
        for (auto f : todos) {
            ok = 1;
            ans++;
            for (int i = 0; i < k; i++) curr[i] += u[f][i];
        }
        todos.clear();
    }
    cout << ans << "\n";
}

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