Submission #1199831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199831		ofoz	Topical (NOI23_topical)	C++17	61 / 100	1093 ms	126488 KiB

Main

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

// Equivalent to the Python `higher` function
bool higher(const vector<int>& a, const vector<int>& b) {
    assert(a.size() == b.size());
    for (size_t i = 0; i < a.size(); ++i) {
        if (b[i] > a[i]) return false;
    }
    return true;
}

void kOne(int n, int k) {
    vector<vector<int>> grid(n, vector<int>(k));
    vector<vector<int>> ben(n, vector<int>(k));

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < k; ++j)
            cin >> grid[i][j];

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < k; ++j)
            cin >> ben[i][j];

    vector<pair<int, int>> pairs;
    for (int i = 0; i < n; ++i)
        pairs.push_back({grid[i][0], ben[i][0]});

    sort(pairs.begin(), pairs.end());
    reverse(pairs.begin(), pairs.end());
    int cur = 0, res = 0;
    while (!pairs.empty() && cur >= pairs.back().first) {
        cur += pairs.back().second;
        pairs.pop_back();
        res++;
    }

    cout << res << endl;
}

void solve() {
    int n, k;
    cin >> n >> k;
    if (k == 1) {
        kOne(n, k);
        return;
    }
    vector<int> cur(k, 0);  // Current values
    vector<pair<vector<int>, int>> a;  // Vector of (arr, index)
    vector<vector<int>> b(n);          // Second matrix

    // Read 'a'
    for (int i = 0; i < n; ++i) {
        vector<int> temp(k);
        for (int j = 0; j < k; ++j) {
            cin >> temp[j];
        }
        a.push_back({temp, i});
    }

    // Read 'b'
    for (int i = 0; i < n; ++i) {
        b[i].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> b[i][j];
        }
    }

    int res = 0;
    for (int iter = 0; iter < n; ++iter) {
        bool found = false;
        vector<pair<vector<int>, int>> nxt;

        for (const auto& p : a) {
            const vector<int>& arr = p.first;
            int i = p.second;

            if (found) {
                nxt.push_back(p);
                continue;
            }

            if (higher(cur, arr)) {
                for (int j = 0; j < k; ++j) {
                    cur[j] += b[i][j];
                }
                found = true;
                ++res;
                continue;
            }

            nxt.push_back(p);
        }

        a = nxt;
    }

    cout << res << endl;
}

signed main() {
    solve();
    return 0;
}

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