Submission #1168390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168390		altern23	Topical (NOI23_topical)	C++20	33 / 100	533 ms	189684 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), isi[k + 5];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++) isi[j].push_back(i);
        }
        for(int i = 1; i <= k; i++){
            sort(isi[i].begin(), isi[i].end(), [&](ll a, ll b){
                return r[a][i] > r[b][i];
            });
        }
        vector<ll> p(k + 5);
        auto check = [&](ll idx){
            for(int i = 1; i <= k; i++){
                if(p[i] < r[idx][i]) return false;
            }
            for(int i = 1; i <= k; i++) p[i] += u[idx][i];
            return true;
        };

        for(;true;){
            bool ok = 0;
            for(int j = 1; j <= k; j++){
                while(isi[j].size() && vis[isi[j].back()]) isi[j].pop_back();
                while(isi[j].size() && check(isi[j].back())){
                    ok = 1;
                    vis[isi[j].back()] = 1;
                    isi[j].pop_back();
                }
            }
            if(!ok) break;
        }

        ll ans = 0;
        for(int i = 1; i <= n; i++) ans += vis[i];
        cout << ans << "\n";
    }   
}

/*

*/ 

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