Submission #1317555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317555		Zone_zonee	Topical (NOI23_topical)	C++20	100 / 100	427 ms	107576 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6+10;

priority_queue<pair<ll, int>> pq[N];
int cnt[N];
ll p[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<vector<ll>> a(n+1, vector<ll>(k+1, 0));
    for(int i = 1; i <= n; ++i) for(int j = 1, x; j <= k; ++j) cin >> x, pq[j].push({-x, i});
    for(int i = 1; i <= n; ++i) for(int j = 1, x; j <= k; ++j) cin >> a[i][j];
    int res = 0;
    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = 1; i <= k; ++i){
            p[i] += a[u][i];
            while(!pq[i].empty()){
                auto [x, idx] = pq[i].top();
                x = -x;
                if(p[i] >= x){
                    if(++cnt[idx] >= k) res++, q.push(idx);
                    pq[i].pop();
                }else{
                    break;
                }
            }
        }
    }
    // for(int i = 1; i <= k; ++i) cout << p[i] << ' ';
    cout << res << '\n';
}

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