Submission #1281389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281389		cheska	Topical (NOI23_topical)	C++20	100 / 100	403 ms	141260 KiB

Main

//dominater orz
//evenvalue orz
//roumak orz
//melody orz
//cpp orz
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<pii, pii> 
#define tiii tuple<int, int, int>
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
#define f first
#define s second
#define pb push_back
const int N = 2750132;
const int MOD = 1e9+7;
struct module {
    vector<int> r, u;
    module(int k) {
        r.resize(k);
        u.resize(k);
    }
};
bool comp(module a, module b) {
    for (int i = 0; i < a.r.size(); i++) {
        if (a.r[i] > b.r[i]) return false;
    }
    return true;
}
signed main() {
   // freopen("in.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k; cin >> n >> k;
    vector<module> a(n, module(k));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) cin >> a[i].r[j];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) cin >> a[i].u[j];
    }
    vector<vector<pii>> b(k, vector<pii>(n));
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n; j++) {
            b[i][j] = {a[j].r[i], j};
        }
        sort(b[i].begin(), b[i].end());
    }
    queue<int> q;
    int ans = 0;
    vector<int> c(n), cr(k), cr2(k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            if (a[i].r[j] == 0) c[i]++;
        }
        if (c[i] == k) {
            q.push(i);
        }
    }
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < n; j++) {
            if (b[i][j].f != 0) {
                cr2[i] = j;
                break;
            }
        }
    }
    while (!q.empty()) {
        int i = q.front(); q.pop();
        ans++;
        for (int j = 0; j < k; j++) {
            cr[j] += a[i].u[j];
            while (cr2[j] < n && b[j][cr2[j]].f <= cr[j]) {
                c[b[j][cr2[j]].s]++;
                if (c[b[j][cr2[j]].s] == k) {
                    q.push(b[j][cr2[j]].s);
                }
                cr2[j]++;
            }
        }
    }
    cout << ans;
}

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