Submission #1171099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171099		KhoaDuy	Topical (NOI23_topical)	C++17	100 / 100	212 ms	74720 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;
    cin >> n >> k;
    int r[n][k],u[n][k];
    long long sum[k]={0};
    vector<vector<pair<int,int>>> order(k);
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            cin >> r[i][j];
            order[j].push_back({r[i][j],i});
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            cin >> u[i][j];
        }
    }
    for(int j=0;j<k;j++){
        sort(order[j].begin(),order[j].end());
    }
    vector<int> candi;
    int ptr[k],cnt[n]={0};
    memset(ptr,-1,sizeof(ptr));
    int ans=0;
    while(true){
        for(int i=0;i<k;i++){
            while(ptr[i]+1<order[i].size()&&order[i][ptr[i]+1].first<=sum[i]){
                ptr[i]++;
                cnt[order[i][ptr[i]].second]++;
                if(cnt[order[i][ptr[i]].second]==k){
                    candi.push_back(order[i][ptr[i]].second);
                }
            }
        }
        if(candi.empty()){
            break;
        }
        ans++;
        for(int j=0;j<k;j++){
            sum[j]+=u[candi.back()][j];
        }
        candi.pop_back();
    }
    cout << ans;
}

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