제출 #1147762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147762		fatman87878	Topical (NOI23_topical)	C++20	100 / 100	316 ms	91800 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=1e6+5;

int n,k,ptr[maxN],vals[maxN],deg[maxN],ans;

vector<pair<int,int>> adj[maxN];

queue<int> q;

int main(){
    IOS
    cin>>n>>k;
    vector val(n+1,vector(k,0ll));
    for(int i = 1;i<=n;i++)for(int j = 0;j<k;j++){
        int v;cin>>v;
        adj[j].emplace_back(v,i);
    }
    for(int i = 1;i<=n;i++)for(ll& j:val[i])cin>>j;
    for(int i = 0;i<k;i++)sort(all(adj[i]));
    q.emplace(0);
    for(int idx;!q.empty();){
        idx = q.front(),q.pop();
        ans++;
        for(int i = 0;i<k;i++){
            vals[i]+=val[idx][i];
            while(ptr[i]<adj[i].size()){
                auto [v,id] = adj[i][ptr[i]];
                if(v>vals[i])break;
                if(++deg[id]==k)q.emplace(id);
                ptr[i]++;
            }
        }
    }
    cout<<ans-1<<'\n';
}

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