제출 #1168423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168423		altern23	Topical (NOI23_topical)	C++20	100 / 100	744 ms	196984 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 1e5;
const ll INF = 4e18;
const ll MOD = 998244353;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, k; cin >> n >> k;
        vector<vector<ll>> r(n + 5, vector<ll>(k + 5)), u(n + 5, vector<ll>(k + 5));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++) cin >> r[i][j];
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++) cin >> u[i][j];
        }
        vector<ll> vis(n + 5);
        priority_queue<pii, vector<pii>, greater<pii>> isi[k + 5];

        for(int i = 1; i <= n; i++) isi[1].push({r[i][1], i});

        vector<ll> p(k + 5);
        auto add = [&](ll idx){
            for(int i = 1; i <= k; i++) p[i] += u[idx][i];
        };

        ll ans = 0;
        for(;true;){
            bool ok = 0;
            // for(int i = 1; i <= k; i++) cout << p[i] << " \n"[i == k];
            for(int j = 1; j <= k; j++){
                while(!isi[j].empty() && isi[j].top().fi <= p[j]){
                    if(j == k){
                        ok = 1, ans++;
                        add(isi[j].top().sec);
                    }
                    else{
                        isi[j + 1].push({r[isi[j].top().sec][j + 1], isi[j].top().sec});
                    }
                    isi[j].pop();
                }
            }
            if(!ok) break;
        }

        cout << ans << "\n";
    }   
}

/*

*/ 

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