Submission #914257

#	Time	Username	Problem	Language	Result	Execution time	Memory
914257		esomer	Topical (NOI23_topical)	C++17	100 / 100	483 ms	152000 KiB

Main

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

void solve(){
    int n, k; cin >> n >> k;
    vector<vector<int>> r(n, vector<int>(k));
    vector<vector<int>> u(n, vector<int>(k));
    for(vector<int>&v : r){
        for(int& x : v) cin >> x;
    }
    for(vector<int>&v : u){
        for(int& x : v) cin >> x;
    }
    r.push_back(vector<int>(k, 0));
    u.push_back(vector<int>(k, 0));
    vector<vector<pair<int, int>>> topics(k);
    for(int j = 0; j < k; j++){
        for(int i = 0; i < n; i++){
            topics[j].push_back({r[i][j], i});
        }
        sort(topics[j].begin(), topics[j].end());
    }
    vector<int> lst(k, -1), cnt(n, 0);
    queue<int> q; q.push(n);
    vector<int> curr(k, 0);
    int ans = 0;
    // cerr << "here" << endl;
    while(!q.empty()){
        int x = q.front(); q.pop();
        ans++;
        for(int i = 0; i < k; i++){
            curr[i] += u[x][i];
            int nw = lst[i]+1;
            while(nw < n && topics[i][nw].first <= curr[i]){
                lst[i]=nw;
                cnt[topics[i][nw].second]++;
                if(cnt[topics[i][nw].second] == k) q.push(topics[i][nw].second);
                nw++;
            }
        }
    }
    cout << ans - 1 << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // int tt; cin >> tt;
    int tt = 1;
    while(tt--) solve();
}

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