Submission #893320

#	Time	Username	Problem	Language	Result	Execution time	Memory
893320		vjudge1	Topical (NOI23_topical)	C++17	100 / 100	544 ms	154672 KiB

Main

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

const int N=1e6;
vector<vector<int>> a,b;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq[N+1];
int cnt[N+1];
int val[N+1];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    a.resize(n+1);
    b.resize(n+1);
    for(int i=1;i<=n;++i)
    {
        a[i].resize(k+1);
        for(int j=1;j<=k;++j)
        {
            cin >> a[i][j];
            pq[j].push({a[i][j], i});
        }
    }
    for(int i=1;i<=n;++i)
    {
        b[i].resize(k+1);
        for(int j=1;j<=k;++j)
        {
            cin >> b[i][j];
            //pq[j].push({a[i][j], i});
        }
    }
    queue<int> q;
    for(int j=1;j<=k;++j)
    {
        while(!pq[j].empty() && pq[j].top().first<=val[j])
        {
            auto p = pq[j].top();
            pq[j].pop();
            cnt[p.second]++;
            if(cnt[p.second]==k) q.push(p.second);
        }
    }
    int kq=0;
    while(!q.empty())
    {
        while(!q.empty())
        {
            kq++;
            int i = q.front();
            q.pop();
            for(int j=1;j<=k;++j) val[j]+=b[i][j];
        }
        for(int j=1;j<=k;++j)
        {
            while(!pq[j].empty() && pq[j].top().first<=val[j])
            {
                auto p = pq[j].top();
                pq[j].pop();
                cnt[p.second]++;
                if(cnt[p.second]==k) q.push(p.second);
            }
        }
    }
    cout << kq;
}

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