Submission #1282736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282736		MisterReaper	Topical (NOI23_topical)	C++20	100 / 100	526 ms	121748 KiB

Main

// File A.cpp created on 23.10.2025 at 21:56:53
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, K;
    std::cin >> N >> K;

    std::vector<std::vector<int>> R(N, std::vector<int>(K));
    std::vector<std::vector<int>> U(N, std::vector<int>(K));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < K; ++j) {
            std::cin >> R[i][j];
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < K; ++j) {
            std::cin >> U[i][j];
        }
    }

    std::vector<i64> sum(K);

    std::vector<int> act(N);
    std::vector<int> pntr(K);
    std::vector<std::vector<int>> ids(K, std::vector<int>(N));

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < K; ++j) {
            ids[j][i] = i;
        }
    }

    std::queue<int> que;

    for (int i = 0; i < K; ++i) {
        std::sort(ids[i].begin(), ids[i].end(), [&](auto lhs, auto rhs) {
            return R[lhs][i] < R[rhs][i];
        });
        while (pntr[i] != N && R[ids[i][pntr[i]]][i] <= sum[i]) {
            if (++act[ids[i][pntr[i]]] == K) {
                que.emplace(ids[i][pntr[i]]);
            }
            ++pntr[i];
        }
    }

    int ans = 0;
    while (!que.empty()) {
        auto p = que.front();
        que.pop();
        ans += 1;
        for (int i = 0; i < K; ++i) {
            sum[i] += U[p][i];
            while (pntr[i] != N && R[ids[i][pntr[i]]][i] <= sum[i]) {
                if (++act[ids[i][pntr[i]]] == K) {
                    que.emplace(ids[i][pntr[i]]);
                }
                ++pntr[i];
            }
        }
    }

    std::cout << ans << '\n';

    return 0;
}

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