Submission #1102455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102455		ShadowShark	Topical (NOI23_topical)	C++17	100 / 100	359 ms	92052 KiB

Main

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

const int maxN = 1e6 + 5;
bool cmp(pair<int, int> A, pair<int, int> B) {
    return A.first > B.first;
}
vector<int> inc[maxN];
vector<pair<int, int>> col[maxN];
int cnt[maxN], skill[maxN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            int x;
            cin >> x;

            col[j].push_back({x, i});
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++) {
            int x;
            cin >> x;

            inc[i].push_back(x);
    }

    for (int i = 1; i <= k; i++)
        sort(col[i].begin(), col[i].end(), cmp);


    int ans = 0;
    queue<int> Q;
    do {
        for (int i = 1; i <= k; i++) {
            if (col[i].size() == 0) continue ;
            while (col[i].size() > 0) {
                auto it = col[i].back();
                if (it.first <= skill[i]) {
                    col[i].pop_back();
                    cnt[it.second]++;
                    if (cnt[it.second] == k) Q.push(it.second);
                }
                else break;
            }
        }

        if (Q.size() == 0) break;
        while (Q.size() != 0) {
            int id = Q.front(); Q.pop();
            for (int i = 1; i <= k; i++)
                skill[i] += inc[id][i - 1];
            ans++;
        }
    } while (true);

    cout << ans;
    return 0;
}

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