Submission #1292425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292425		1ota	Topical (NOI23_topical)	C++20	40 / 100	1105 ms	196092 KiB

Main

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

#define endl "\n"
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()

const int inf = 9e18;

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, k; cin >> n >> k;

    vector<vector<int>> a(n, vector<int>(k, 0)), b(n, vector<int>(k, 0));
    for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) cin >> a[i][j];
    for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) cin >> b[i][j];

    vector<vector<pii>> t(k, vector<pii>(n));
    for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) t[j][i] = pii{a[i][j], i};
    for (int i = 0; i < k; i++) sort(entire(t[i]));

    int ans = 0;
    vector<int> c(n, 0), idx(k, 0), cur(k, 0);

    set<pii, greater<pii>> lesson;
    auto inc = [&](int i, int newc){
        lesson.erase(pii{c[i], i});
        c[i] = newc;
        lesson.insert(pii{c[i], i}); 
    };

    auto update = [&](){
        for (int i = 0; i < k; i++){
            while (idx[i] < n and t[i][idx[i]].ff <= cur[i]) inc(t[i][idx[i]].ss, c[t[i][idx[i]].ss] + 1), idx[i]++;
        }
    };

    for (int i = 0; i < n; i++) inc(i, 0);


    auto add = [&](){
        auto [ci, i] = *lesson.begin();
        if (ci == k){
            inc(i, -inf);
            for (int j = 0; j < k; j++) cur[j] += b[i][j];
            return true;
        }
        return false;
    };

    for (int i = 0; i < n; i++){
        update();
        if (!add()) break;
        ans++;
    }

    cout << ans << endl;

    return 0;
}

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