Submission #1177310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177310		VMaksimoski008	Topical (NOI23_topical)	C++20	100 / 100	478 ms	70708 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

signed main() {
    int n, m, ans = 0; cin >> n >> m;
    vector<pair<int, int> > mn[m+1];
    int mat[n+1][m+1];

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            int x; cin >> x;
            mn[j].push_back({ x, i });
        }
    }

    for(int j=1; j<=m; j++)
        sort(mn[j].rbegin(), mn[j].rend());

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) cin >> mat[i][j];

    vector<int> deg(n+1);
    vector<ll> curr(m+1, 0);

    queue<int> q;
    for(int i=1; i<=m; i++) {
        while(!mn[i].empty() && mn[i].back().first <= curr[i]) {
            deg[mn[i].back().second]++;
            mn[i].pop_back();
        }
    }

    for(int i=1; i<=n; i++) {
        if(deg[i] == m) {
            q.push(i);
        }
    }

    while(!q.empty()) {
        int u = q.front(); q.pop(); ans++;
        for(int i=1; i<=m; i++) curr[i] += mat[u][i];

        for(int i=1; i<=m; i++) {
            while(!mn[i].empty() && mn[i].back().first <= curr[i]) {
                if(++deg[mn[i].back().second] == m) q.push(mn[i].back().second);
                mn[i].pop_back();
            }
        }
    }

    cout << ans << '\n';
}

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