Submission #1099204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099204		NoMercy	Topical (NOI23_topical)	C++17	100 / 100	416 ms	137904 KiB

Main

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

typedef long long ll;

bool cmp (array<int, 2> a, array<int, 2> b) {
    if (a[0] == b[0]) return a[1] < b[1];
    return a[0] > b[0];
}

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N, M;
    cin >> N >> M;
    vector<vector<int>> r(N, vector<int> (M, 0)), u(N, vector<int> (M, 0));
    vector<int> say(N, 0), p(M, 0);
    queue<int> q;
    vector<vector<array<int, 2>>> tmp(M);
    for (int i = 0;i < N;i ++) {
        for (int j = 0;j < M;j ++) {
            cin >> r[i][j];
            if (r[i][j] == 0) {
                say[i] ++;
            }
            tmp[j].push_back({r[i][j], i});
        }
        if (say[i] == M) {
            q.push(i);
        }
    }
    for (int i = 0;i < N;i ++) {
        for (int j = 0;j < M;j ++) {
            cin >> u[i][j];
        }
    }
    for (int j = 0;j < M;j ++) {
        sort (tmp[j].begin(), tmp[j].end(), cmp);
    }
    int result = 0;
    while (q.size() > 0) {
        auto it = q.front();
        q.pop();
        result ++;
        for (int j = 0;j < M;j ++) {
            p[j] += u[it][j];
            while (tmp[j].size() > 0 && tmp[j].back()[0] <= p[j]) {
                say[tmp[j].back()[1]] ++;
                if (say[tmp[j].back()[1]] == M) {
                    q.push(tmp[j].back()[1]);
                }
                tmp[j].pop_back();
            }
        }
    }
    cout << result << "\n";
}

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