Submission #1134618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134618		Luvidi	Topical (NOI23_topical)	C++20	100 / 100	465 ms	82276 KiB

Main

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

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

void solve() {
    int n,k;
    cin>>n>>k;
    vector<vector<ll>> a(n,vector<ll>(k));
    priority_queue<pll> pq[k];
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            int x;
            cin>>x;
            pq[j].push({-x,i});
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            cin>>a[i][j];
        }
    }
    ll c[n],ans=0,s[k];
    memset(c,0,sizeof(c));
    memset(s,0,sizeof(s));
    vector<int> st;
    auto f=[&](){
        for(int i=0;i<k;i++){
            while(!pq[i].empty()&&-pq[i].top().fs<=s[i]){
                int x=pq[i].top().sc;
                if((++c[x])==k)st.pb(x);
                pq[i].pop();
            }
        }
    };
    f();
    while(!st.empty()){
        int v=st.back();
        st.pop_back();
        ans++;
        for(int i=0;i<k;i++)s[i]+=a[v][i];
        f();
    }
    cout<<ans<<'\n';
}

int main() {
    #ifdef FPO
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}

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