Submission #1271577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271577		hungdt	Topical (NOI23_topical)	C++20	100 / 100	349 ms	68452 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxk = 1e6 + 5;
const int maxn = 1e6 + 5;
int n, k;
vector<pair<int, int>> r[maxk];
int a[maxk];
vector<int> u[maxn];
int cnt[maxn];
int ans;
int ptr[maxk];
queue<int> q;

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

    cin >> n >> k;

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

    for (int i=1; i<=n; i++){
        u[i].push_back(0);
        for (int j=1; j<=k; j++){
            int x;
            cin >> x;
            u[i].push_back(x);
        }
    }

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

    for (int i=1; i<=k; i++){
        while (ptr[i] < r[i].size() && r[i][ptr[i]].first <= a[i]){
            cnt[r[i][ptr[i]].second]++;
            ptr[i]++;
        }
    }

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

    while (!q.empty()){
        int node = q.front();
        q.pop();
        ans++;
        for (int i=1; i<=k; i++) a[i] += u[node][i];

        for (int i=1; i<=k; i++){
            while (ptr[i] < r[i].size() && r[i][ptr[i]].first <= a[i]){
                cnt[r[i][ptr[i]].second]++;
                if (cnt[r[i][ptr[i]].second] == k) q.push(r[i][ptr[i]].second);
                ptr[i]++;
            }
        }
    }

    cout << ans;

    return 0;
}

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