Submission #1013984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013984		Ariadna	Topical (NOI23_topical)	C++14	100 / 100	632 ms	142000 KiB

Main

#include <bits/stdc++.h>
#define pb push_back

using namespace std;


int n, k;
vector<vector<int>> r, u;

int modules() {
    queue<int> q;
    int cnt = 0;
    vector<vector<pair<int, int>>> m(k);
    vector<int> knowledge(k), completed(k);
    vector<int> m_completed(n, 0), visited(n, 0);
    for (int i = 0; i < n; ++i) {
        bool done = 1;
        for (int j = 0; j < k; ++j) {
            if (r[i][j] > 0) done = 0;
            m[j].pb({r[i][j], i});
        }
        if (done) {
            q.push(i);
            visited[i] = true;
        }
    }

    if (q.empty()) return 0;

    for (int i = 0; i < k; ++i) sort(m[i].begin(), m[i].end());
    while (!q.empty()) {
        int mod = q.front();
        q.pop();
        ++cnt;
        for (int i = 0; i < k; ++i) {
            knowledge[i] += u[mod][i];

            while (completed[i] < n && m[i][completed[i]].first <= knowledge[i]) {
                if (++m_completed[m[i][completed[i]].second] == k && !visited[m[i][completed[i]].second]) {
                    q.push(m[i][completed[i]].second);
                    visited[m[i][completed[i]].second] = true;
                }
                ++completed[i];
            }
        }
    }

    return cnt;
}

int main() {
    cin >> n >> k;
    r = u = vector<vector<int>>(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];
        }
    }

    cout << modules() << '\n';

    return 0;
}

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