제출 #1169603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169603		trashaccount	Topical (NOI23_topical)	C++20	100 / 100	552 ms	121072 KiB

Main

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

#define isz(a) (int)(a).size()

int n, k;
vector <vector <int> > r, u;
vector <vector <int> > arr;
vector <int> ptr, p, cnt;

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

    cin >> n >> k;
    r.assign(n, vector <int>(k));
    u.assign(n, vector <int>(k));
    arr.assign(k, {});
    p.assign(k, 0);
    ptr.assign(k, 0);
    cnt.assign(n, 0);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++){
            cin >> r[i][j];
            arr[j].push_back(i);
        }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
            cin >> u[i][j];

    for (int i = 0; i < k; i++){
        sort(arr[i].begin(), arr[i].end(), [&](int x, int y){
            return r[x][i] < r[y][i];
        });
    }

    int ans = 0;
    while (true){
        vector <int> clist = {};
        for (int i = 0; i < k; i++){
            while (ptr[i] < n){
                int t = arr[i][ptr[i]];
                if (p[i] >= r[t][i]){
                    cnt[t]++;
                    if (cnt[t] == k) clist.push_back(t);
                }
                else break;

                ptr[i]++;
            }
        }
        if (clist.empty()) break;
        ans += isz(clist);
        for (int t : clist){
            for (int i = 0; i < k; i++) p[i] += u[t][i];
        }
    }
    cout << ans;
    return 0;
}

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